Monotone stack and its application

---

The concept of monotone stack

Monotone stack is a special kind of stack , As the name suggests, the data stored in the stack is orderly , So it can be divided into monotonic increasing stack and monotonic decreasing stack .

• Monotonically increasing stacks ： Monotonically increasing stack is from the bottom of the stack to the top of the stack, and the data is from large to small , That is, the large value is below , Small value above .
• Monotonically decreasing stacks ： Monotonically decreasing stack means that the data from the bottom of the stack to the top of the stack is from small to large , That is, the small value is below , The big value is above .
  

Take monotonically increasing stack as an example , Its pseudo code is ：

stack<int> st;
// Here, you generally need to add an end flag to the end of the array , The following examples will be explained in detail 
for ( Traverse the array )
{
    
	while ( Stack is not empty.  &&  The stack top element is smaller than the current element )
	{
    
		 Stack top element out of stack ;
		 Update results ;
	}
	 Current data stack ;
}
// Here, the data in the stack is from large to small from the bottom to the top of the stack , They need to be ejected and processed 
while ( Stack is not empty. )
{
    
	 Stack top element out of stack ;
	 Update results ;
}

---

Application of monotone stack

CD101 Monotone stack structure （ No repetition value ）

CD101 Monotone stack structure
This problem requires us to find the subscript of the first smaller number on the left and right of each number in the array , We maintain a monotonically decreasing stack , When the data on the stack x Than the data at the top of the stack y Hours , Pop up the data at the top of the stack y,y The smaller data on the right is x, The smaller data on the left is y The number pressed below z; If x Than y Big , be y Don't pop up ,x Push .

So the code is as follows ：

#include<iostream>
#include<vector>
#include<stack>
#include<list>
using namespace std;
// There are no duplicate values in the array 
vector<vector<int>> getNearLessNoRepeat(const vector<int>& arr)
{
    
	//res Subscript used to record the number of left and right elements smaller than the top of the stack 
	vector<vector<int>>res(arr.size(), vector<int>(2));
	stack<int> st;
	for (int i = 0; i < arr.size(); i++)
	{
    
		// The stack is not empty and arr[i] Smaller than the number at the top of the stack , explain arr[i] Is the first number on the right that is smaller than the top of the stack 
		while (!st.empty() && arr[st.top()] > arr[i])
		{
    
			// The subscript of the left popup number 
			int pop_index = st.top();
			st.pop();
			
			// Update results 
			// If the stack is empty , Then the index of the small number on the left of the pop-up number is -1, Otherwise, it is the subscript at the top of the stack 
			int left_index = st.empty() ? -1 : st.top();
			res[pop_index][0] = left_index;
			res[pop_index][1] = i;
		}
		st.push(i);
	}
	// Stack is not empty. , At this point, all the numbers in the stack , There is no smaller number on their right 
	// The number smaller than them on the left is the number at the top of the next stack 
	while (!st.empty())
	{
    
		// Pop up the subscript of the top of the stack 
		int pop_index = st.top();
		st.pop();
		// If the stack is empty , Then the index of the small number on the left of the pop-up number is -1, Otherwise, it is the subscript at the top of the stack 
		int left_index = st.empty()? -1 : st.top();
		res[pop_index][0] = left_index;
		res[pop_index][1] = -1;
	}
	return res;
}
int main()
{
    
    int n=0;
    cin>>n;
	vector<int>arr(n,0);
    for(int i=0;i<n;i++)
    {
    
        cin>>arr[i];
    }
	vector<vector<int>>ans = getNearLessNoRepeat(arr);
	for (int i = 0; i < ans.size(); i++)
	{
    
        // Use printf than cout More efficient 
        printf("%d %d\n",ans[i][0],ans[i][1]);
		//cout << ans[i][0] << " " << ans[i][1] << endl;

	}
}

CD188 Monotone stack structure ( There are duplicate values )

CD188 Monotone stack structure ( Advanced )
This question is similar to the previous one , The main reason is that there are many duplicate values , We can put the subscripts of repeated values into a linked list , When updating, directly update all subscripts in the linked list .

#include<iostream>
#include<vector>
#include<stack>
#include<list>
using namespace std;
// There are duplicate values in the array 
vector<vector<int>> getNearLess(const vector<int>& arr)
{
    
	vector<vector<int>>res(arr.size(), vector<int>(2));
	// Store the linked list in the stack , Because we need to put the repeated subscripts in the linked list 
	stack<list<int>> st;
	for (int i = 0; i < arr.size(); i++)
	{
    
		// The stack is not empty and arr[i] Smaller than the number at the top of the stack , explain arr[i] Is the first number on the right that is smaller than the top of the stack 
		while (!st.empty() && arr[st.top().back()] > arr[i])
		{
    
			list<int> pop_index_list = st.top();
			st.pop();
			int left_index = st.empty() ? -1 : st.top().back();
			for (auto& pop_index : pop_index_list)
			{
    
				res[pop_index][0] = left_index;
				res[pop_index][1] = i;
			}
		}
		// Stack is not empty. , also arr[i] Equal to the number at the top of the stack , Then insert it behind the linked list at the top of the stack 
		if (!st.empty()&&arr[st.top().back()] == arr[i])
		{
    
			st.top().push_back(i);
		}
		// The stack is empty. , Or the current element is larger than the element in the linked list at the top of the stack 
		// Will i Form a linked list and put it on the stack 
		else
		{
    
			st.push(list<int>{
    i});
		}
	}
	// At this point, all the numbers in the stack , There is no smaller number on the right side of the array ,
	// On the left is the subscript of the last node of the linked list they are pressing 
	while (!st.empty())
	{
    
		list<int> pop_index_list = st.top();
		st.pop();
		int left_index = st.empty() ? -1 : st.top().back();
		for (auto& pop_index : pop_index_list)
		{
    
			res[pop_index][0] = left_index;
			res[pop_index][1] = -1;
		}
	}
	return res;
}
int main()
{
    
    int n=0;
    cin>>n;
	vector<int>arr(n,0);
    for(int i=0;i<n;i++)
    {
    
        cin>>arr[i];
    }
	vector<vector<int>>ans = getNearLess(arr);
	for (int i = 0; i < ans.size(); i++)
	{
    
        printf("%d %d\n",ans[i][0],ans[i][1]);
		//cout << ans[i][0] << " " << ans[i][1] << endl;

	}
}

496. Next bigger element I

Next bigger element I

class Solution {
    
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    
        vector<int>res(nums1.size());
        map<int,int>m;
        stack<int>stk;
        for(int i=0;i<nums2.size();i++)
        {
    
            while(!stk.empty()&&nums2[i]>stk.top())
            {
    
                m[stk.top()]=nums2[i];
                stk.pop();
            }
            stk.push(nums2[i]);
        }
        while(!stk.empty())
        {
    
            m[stk.top()]=-1;
            stk.pop(); 
        }
        for(int i=0;i<nums1.size();i++)
        {
    
            res[i]=m[nums1[i]];
        }
        return res;
    }
};

739. Daily temperature

739. Daily temperature

class Solution {
    
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
    
        int size=temperatures.size();
        vector<int>res(size,0);
        stack<int>st;
        for(int i=0;i<size;i++)
        {
    
            while(!st.empty()&&temperatures[i]>temperatures[st.top()])
            {
    
                int left=st.top();
                st.pop();
                res[left]=i-left;
            }
            st.push(i);
        }
        return res;
    }
};

1856. The maximum value of the smallest product of subarrays

1856. The maximum value of the smallest product of subarrays

This is a prefix and + Monotonic stack problem , We use monotonically decreasing stack , Assume that the current stack value is x, Top element of stack y Than x Small , here x The subscript -1 And y The subscript of the pressed element is in the interval with y Is a subarray of minimum values , Use the prefix and to sum the subarray , And then use y Multiply .

class Solution {
    
public:
    int maxSumMinProduct(vector<int>& nums) {
    
        int size=nums.size();
        //sums Save the prefix and 
        vector<long long> sums(size,0);
        sums[0]=nums[0];
        for(int i=1;i<size;i++)
        {
    
            sums[i]=sums[i-1]+nums[i];
        }
        long long res=INT_MIN;
        //st For monotone stack , Save array subscript , When nums[i] Smaller than the value corresponding to the subscript of the element at the top of the stack , Out of the stack 
        stack<int> st;
        for(int i=0;i<size;i++)
        {
    
            while(!st.empty()&&nums[st.top()]>=nums[i])
            {
    
                long long num=nums[st.top()];
                st.pop();
                long long left_sum=st.empty()?sums[i-1]:sums[i-1]-sums[st.top()];
                res=max(res,num*left_sum);
            }
            st.push(i);
        }
        // At this point, all the numbers in the stack , None of them has a smaller number on the right , Because if there is , They will come out of the stack in the previous step 
        // So the range of the subarray is size-1~st.top()
        while(!st.empty())
        {
    
            long long num=nums[st.top()];
            st.pop();
            long long left_sum=st.empty()?sums[size-1]:sums[size-1]-sums[st.top()];
            res=max(res,num*left_sum);
        }
        return (int)(res%1000000007);
    }

};

84. The largest rectangle in the histogram

84. The largest rectangle in the histogram
This question is similar to the previous one , The last question is to find the interval sum of a subarray . This problem is also to find the difference of the subscript of an interval .

class Solution {
    
public:
    int largestRectangleArea(vector<int>& heights) {
    
        if(heights.size()==1)
        {
    
            return heights[0];
        }
        int size=heights.size();
        int res=INT_MIN;
        //st For monotone stack , Save array subscript , When nums[i] Smaller than the value corresponding to the subscript of the element at the top of the stack , Out of the stack 
        stack<int> st;
        for(int i=0;i<size;i++)
        {
    
            while(!st.empty()&&heights[st.top()]>=heights[i])
            {
    
                int num=heights[st.top()];
                st.pop();
                int left_sum=st.empty()?i:i-1-st.top();
                res=max(res,num*left_sum);
            }
            st.push(i);
        }
        while(!st.empty())
        {
    
            int num=heights[st.top()];
            st.pop();
            int left_sum=st.empty()?size:size-1-st.top();
            res=max(res,num*left_sum);
        }
        return res;
    }
};

85. The largest rectangle

85. The largest rectangle
By enumerating submatrix, the 0 Behavior of the foundation , It contains only 1 The area of the largest rectangle , Then enumerate to 1 Behavior of the foundation , Repeat the process , It can be calculated that only 1 The area of the largest rectangle . The way to calculate the area is the last question .

class Solution {
    
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
    
        int res=INT_MIN;
        int row=matrix.size();
        int col=matrix[0].size();
        vector<int>temp(col,0);
        // The foundation 
        for(int i=0;i<row;i++)
        {
    
        	// When the foundation is 0 when , The height of the rectangle is 0
            for(int j=0;j<col;j++)
            {
    
                if(matrix[i][j]=='0')
                {
    
                    temp[j]=0;
                }
                else
                {
    
                    temp[j]+=1;
                }
            }
            // Find out to i Is the area of the largest rectangle of the foundation 
            int temp_res=largestRectangleArea(temp);
            res=max(res,temp_res);
        }
        return res;
    }
    int largestRectangleArea(vector<int>& heights) {
    
        if(heights.size()==1)
        {
    
            return heights[0];
        }
        int size=heights.size();
        int res=INT_MIN;
        //st For monotone stack , Save array subscript , When nums[i] Smaller than the value corresponding to the subscript of the element at the top of the stack , Out of the stack 
        stack<int> st;
        for(int i=0;i<size;i++)
        {
    
            while(!st.empty()&&heights[st.top()]>=heights[i])
            {
    
                int num=heights[st.top()];
                st.pop();
                int left_sum=st.empty()?i:i-1-st.top();
                res=max(res,num*left_sum);
            }
            st.push(i);
        }
        while(!st.empty())
        {
    
            int num=heights[st.top()];
            st.pop();
            int left_sum=st.empty()?size:size-1-st.top();
            res=max(res,num*left_sum);
        }
        return res;
    }
};

1504. The statistics are complete 1 Sub rectangle

1504. The statistics are complete 1 Sub rectangle
This question is similar to the last one , The difference is that the last question only asks for the largest submatrix , And this is the number of submatrixes .
We still use “ The foundation ” The idea of , According to the mathematical formula , We can roll out when there is only one line full 1 And its width is n when , The number of submatrix is (n+1)*n/2, Then we just need to calculate the subscript of the smallest number on the left and right of the column , Then we can find the height of the submatrix whose height is the column , Then multiply the height by the number of columns , Is the number of submatrixes of the rectangle .

class Solution {
    
public:
    int numSubmat(vector<vector<int>>& mat) {
    
        int row=mat.size();
        int col=mat[0].size();
        int res=0;
        vector<int>temp(col,0);
        for(int i=0;i<row;i++)
        {
    
            for(int j=0;j<col;j++)
            {
    
                if(mat[i][j]==0)
                {
    
                    temp[j]=0;
                }
                else
                {
    
                    temp[j]+=1;
                }
            }
            res+=proecss(temp);
        }
        return res;
    }
    int proecss(vector<int>& heights) {
    
        if(heights.size()==1)
        {
    
            return heights[0];
        }
        int size=heights.size();
        int res=0;
        //st For monotone stack , Save array subscript , When nums[i] Smaller than the value corresponding to the subscript of the element at the top of the stack , Out of the stack 
        stack<int> st;
        for(int i=0;i<size;i++)
        {
    
            while(!st.empty()&&heights[st.top()]>=heights[i])
            {
    
            	//cur Is the current subscript , The subscript of the number smaller than it on the left and right sides is i and st.top()
                int cur=st.top();
                st.pop();
                // In order to prevent heights[cur]=heights[i], To screen 
                // The two columns are equal in height , The following columns are calculated 
                if(heights[cur]>heights[i])
                {
    
                    //left Subscript to the small number on the left 
                    int left=st.empty()?-1:st.top();
                    //n Is width ,left Subscript the leftmost smallest number 
                    //i Subscript to the small number on the right 
                    int n=i-left-1;
                    // Calculate the height ,down It is the one with the larger minimum value on the left and right sides 
                    //heights[cur]-down Is the height of the rectangle 
                    int down=max(left==-1?0:heights[left],heights[i]);
                    res+=(heights[cur]-down)*num(n);

                }
            }
            st.push(i);
        }
        while(!st.empty())
        {
    
            int cur=st.top();
            st.pop();
            int left=st.empty()?-1:st.top();
            int n=size-left-1;
            int down=left==-1?0:heights[left];
            res+=(heights[cur]-down)*num(n);

        }
        return res;
    }
    // If the matrix has only one column , And the height of the matrix is n, What does it have num(n) Submatrix 
    int num(int n)
    {
    
        return ((n*(1+n))>>1);
    }
};

907. The sum of the minimum values of a subarray

907. Sum of minimum values of subarray
This problem requires the sum of the minimum values in all subarrays . We can use the monotone stack to find a number x（ Subscript to be a） The subscript of the first smaller number on the left and right （ Subscript to be b and c）, Then we can use it to find x Is the number of subarrays （(a-b)*(c-a)）, The smallest of these subarrays is x, So multiply by x.

Finally, enumerate all the numbers .

When the adjacent numbers are equal , We use the number on the left to knot the number of operator intervals , such as 6 6 6 Three numbers , The leftmost 6 The number of intervals is 3（ The left interval is 1, The right section is 3）, The middle is 2, On the right is 1（ It itself ）.

class Solution {
    
public:
    int sumSubarrayMins(vector<int>& arr) {
    
        //left[i]=x:arr[i] On the left , leave arr[i] lately ,<=arr[i] The position of is x
        vector<int>left=leftNearLessEqual2(arr);
        //left[i]=x:arr[i] On the right , leave arr[i] lately ,<arr[i] The position of is x
        vector<int>right=rightNearLessEqual2(arr);
        long res=0;
        for(int i=0;i<arr.size();i++)
        {
    
            long start=i-left[i];
            long end=right[i]-i;
            res+=start*end*arr[i];
            res%=1000000007;
        }
        return (int)res;
    }
    vector<int> leftNearLessEqual2(vector<int>&arr)
    {
    
        int n=arr.size();
        vector<int>left(n,0);
        stack<int>st;
        for(int i=n-1;i>=0;i--)
        {
    
            while(!st.empty()&&arr[i]<=arr[st.top()])
            {
    
                left[st.top()]=i;
                st.pop();
            }
            st.push(i);
        }
        while(!st.empty())
        {
    
            left[st.top()]=-1;
            st.pop();
        }
        return left;
    }
    vector<int> rightNearLessEqual2(vector<int>&arr)
    {
    
        int n=arr.size();
        vector<int>right(n,0);
        stack<int>st;
        for(int i=0;i<n;i++)
        {
    
            while(!st.empty()&&arr[i]<arr[st.top()])
            {
    
                right[st.top()]=i;
                st.pop();
            }
            st.push(i);
        }
        while(!st.empty())
        {
    
            right[st.top()]=n;
            st.pop();
        }
        return right;
    }
};

1307 · Verify the preorder sequence in the binary search tree

1307 · Verify the preorder sequence in the binary search tree
Preorder traversal follows the order of left and right roots , So the first few numbers are decreasing （ Because we have to traverse the left subtree all the way ）, When increment occurs , It indicates that the right subtree is traversed at this time . Suppose this increasing number is x, But we're not sure x Which parent node is the left child tree , Therefore, we need a monotone stack to record the root nodes decreasing along the way , Then use the number at the top of the stack and x Compare , Less than, pop up , And record the last pop-up stack , The last number that pops up is x Parent node . take x Pressing stack .
After that, the number will be higher than x The parent node of is large , If it's smaller , It does not conform to the rules of preorder traversal .

The following numbers repeat the above process .

class Solution {
    
public:
    /** * @param preorder: List[int] * @return: return a boolean */
    bool verifyPreorder(vector<int> &preorder) {
    
        // write your code here
        stack<int>minStack;
        int lastRoot=INT_MIN;
        for(int i=0;i<preorder.size();i++)
        {
    
            if(preorder[i]<lastRoot)
            {
    
                return false;
            }
            while(!minStack.empty()&&preorder[i]>minStack.top())
            {
    
                lastRoot=minStack.top();
                minStack.pop();
            }
            minStack.push(preorder[i]);
        }
        return true;
    }
};

1008. A binary search tree is constructed by preorder traversal

1008. A binary search tree is constructed by preorder traversal
The left and right traversal order of the root node can make the root node x Quickly find the left subtree node y, Right subtree node z yes x The first one on the right is x Big nodes , So we can use the monotone stack to record this subscript , Then you can build a binary tree .

class Solution {
    
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
    
        int size=preorder.size();
        vector<int>right_first_big(size,-1);
        stack<int>big_stack;
        for(int i=0;i<size;i++)
        {
    
            while(!big_stack.empty()&&preorder[i]>preorder[big_stack.top()])
            {
    
                right_first_big[big_stack.top()]=i;
                big_stack.pop();
            }
            big_stack.push(i);
        }
        return process(preorder,0,size-1,right_first_big);
    }
    TreeNode* process(vector<int>& preorder,int left,int right,vector<int>& right_first_big)
    {
    
        if(left>right)
        {
    
            return nullptr;
        }
        TreeNode* root=new TreeNode(preorder[left]);
        // If the first one on the right is bigger than root The subscript of a large number is -1, shows root Node has no right subtree 
        int right_index=right_first_big[left]==-1?right+1:right_first_big[left];
        root->left=process(preorder,left+1,right_index-1,right_first_big);
        root->right=process(preorder,right_index,right,right_first_big);

        return root;
    }
};

The finger of the sword Offer 33. The post order traversal sequence of binary search tree

The finger of the sword Offer 33. The post order traversal sequence of binary search tree
Postorder traversal follows the principle of left and right roots , If you turn it upside down , The root is right and left , The root right is an increasing sequence , This is the same thing as up here “ Verify the preorder sequence in the binary search tree ” The solution is the same .

class Solution {
    
public:
    bool verifyPostorder(vector<int>& postorder) {
    
        stack<int>big_stack;
        int last_root=INT_MAX;
        for(int i=postorder.size()-1;i>=0;i--)
        {
    
            if(postorder[i]>last_root)
            {
    
                return false;
            }
            while(!big_stack.empty()&&postorder[i]<big_stack.top())
            {
    
                last_root=big_stack.top();
                big_stack.pop();
            }
            big_stack.push(postorder[i]);
        }
        return true;
    }
};