Monotone stack template

Monotonic stack

As the name suggests, the elements in the stack are monotonous .

But how to use this ？ How can it be monotonous ？ Look at the example below

subject
Given a length of N The whole number sequence of , Output the first number smaller than it on the left of each number , If not, output -1.
sample input ：

5
3 4 2 7 5

sample output ：

-1 3 -1 2 2

The meaning of the topic is easy to understand
So let's first look at violent practices , Take one number at a time , Compare with the previous number

for(int i=0;i<n;i++）
{
    
	for(int j=1;j=i;j++)
	{
    
		if(a[j]>=a[j-1])
		{
    
			break;
		}
	}
}

We think about the worst , When the sequence is in descending order , for example ：

5
5 4 3 2 1

5 If you don't go through the cycle
4 Words and 5 Compare
3 And 4 and 5 Compare
2 And 3、4 and 5 Compare
1 And 2、3、4 and 5 Compare

Observation shows that , We need to take out each number , And then go through all the numbers before this number .
The time complexity is O(n^2),oj The data range is n<=1e5, Evaluation machine 1s The amount of internal operation data is 1e8~1e9, We are right. 1e10 The amount of data is unacceptable , So we need to optimize our practices . At this time, we introduce monotone stack .

Take the input sample as an example to simulate a single stack adjustment
3 4 2 7 5

Let's go through... In sequence , Look back from the past

First look at 3, No one smaller than him is put on the stack
Look again 4, Then compare it with the top element of the stack , Find that the conditions are met , Then output the top element of the stack , And then 4 Push
Look again 2, Also compare with the stack top element , But the top of the stack element ratio 2 Big , Then we need pop Out of the stack , Then compare it with the top element of the stack , Until we find the ratio 2 Small elements , Or the stack ends in empty time , Then we need to determine whether the stack is empty , Output when stack is empty -1, If the stack is not empty, it means that a comparison has been found 2 Small elements , That is, the output stack top element , The final will be 2 Push
Look again 7, Compare stack top elements , Less than the top of the stack element , Then enter the top element of the stack , Push
Finally, let's see 5, Compare pop-up stack top elements , Then compare , Find that the conditions are met , Output stack top elements

Let's take another look at the changing process of the elements in the stack
3
3 4
2
2 7
2 5

At this time, you will find that the elements in the stack are monotonically increasing from the bottom of the stack to the top of the stack . That's why it's called a monotone stack ！！！

Template code

#include<iostream>
using namespace std;
const int N=1e5+5;
int a[N],stk[N],n,tt=0;
int main()
{
    
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",a+i);
    for(int i=0;i<n;i++)
    {
    
        while(tt&&a[i]<=stk[tt]) --tt;
        if(tt) printf("%d ",stk[tt]);
        else printf("-1 ");
        stk[++tt]=a[i];
    }
    return 0;
}