Monotonic stack

Luogu P5788 【 Templates 】 Monotonic stack

Title address

https://www.luogu.com.cn/problem/P5788

Title Description

Input

5
1 4 2 3 5

Output

2 5 4 5 0

Monotonic stack ： Every time a new element is put on the stack , The elements in the stack keep orderly monotonic increasing or decreasing

The elements of the array can be compared to the height of an adult , Stand these people in a line , Start with one person , Ask the first person visible behind him
For example, in the example , Elements [4], Compare a height to 4 People who , Then the first person visible behind this person is [5], because [2],[3] Height ratio [4] Short , Is blocked. .

Then start creating monotone stacks ：
Press data from back to front ,[5] Push , Then press in [3], also [2], Because it conforms to the principle of monotonous decline , that [3] The previous number , That is to say, bi [3] The taller one is [5], Than [2] The taller one is [3]. Press in [4] There is a slight change when , because [2],[3] All ratio [4] smaller ( Height ratio [4] Short ), So the [2],[3] All out of the stack , that [4] The previous number is [5], It also conforms to the principle of monotonic decline . And finally [2], Than the stack [4] smaller , Therefore, there is no operation of pressing out the stack , Is directly [4]

The code is as follows ：

#include<iostream>
#include<cstdio>
#include<stack>
#define INF 3000005
using namespace std;
int line[INF], ans[INF];
//line Is an array that stores data ,ans Is an array of answers 
int main(){
    
	int i, n;
	scanf("%d", &n);
	for (i = 0; i < n; i++){
    
		scanf("%d", &line[i]);
	}
	stack<int> s;
	// Scan elements from back to front 
	for (i = n - 1; i >= 0; i--){
    
		while (!s.empty() && line[s.top()] <= line[i]){
    
		// Take two. " tall " Elements between elements are pressed out of the stack , Because they have no meaning to exist 
			s.pop();
		}
		ans[i] = s.empty() ? 0 : (s.top() + 1); // Get the location of the element 
		s.push(i); // Index , Not the elements 
	}
	for (i = 0; i < n - 1; i++){
    
		printf("%d ", ans[i]);
	}
	printf("%d", ans[i]);
	return 0;
}

---

leetcode 503. Next bigger element II

Title address

https://leetcode-cn.com/problems/next-greater-element-ii

Title Description

 Given a circular array （ The next element of the last element is the first element of the array ）, Output the next larger element of each element 
 Numbers  x  The next larger element of is in array traversal order , The first larger number after this number ,
 This means that you should cycle through it to the next larger number . If it doesn't exist , The output  -1.

 Example  1:

	 Input : [1,2,1]
	 Output : [2,-1,2]
	 explain :  first  1  The next larger number of is  2;
		   Numbers  2  Can't find the next larger number ; 
		   the second  1  The next largest number of need to loop search , The result is also  2.

 Be careful :  The length of the input array will not exceed  10000.

Ring array , But computer memory is linear , So we usually use linear array to simulate the effect of circular array , Yes % Operator remainder

The idea of this problem can be ： Put the original array “ Double ”, It's followed by an original array , Then there is the template of monotone stack .

Here is the picture above , It should be easier to understand with the code .

Code

class Solution {
    
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
    
        int i, len = nums.size();
        stack<int> s;
        vector<int> res(len);
        // It can be seen as doubling the length of the array 
        for(i=2*len-1;i>=0;i--){
    
            while(!s.empty() && s.top() <= nums[i%len]) // Remainder 
                s.pop();
            res[i%len] = s.empty() ? -1 : s.top();
            s.push(nums[i%len]);
        }
        return res;
    }
};

The topic of monotonous stack ：

• The largest rectangle in the histogram
• Rainwater collection