What is monotone stack

What is monotone stack

A monotonic stack is a stack that monotonically increases or decreases , That is, increasing or decreasing from the bottom of the stack to the top of the stack , According to this structure of monotone stack , It's easy to think that using monotone stack can easily O(n²) The time complexity is optimized to O(n), If you use arrays , The relative spatial complexity will not be too high

Example

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.

Input format

The first line contains integers N, Represents the length of a sequence .

The second line contains  N  It's an integer , Represents an integer sequence .

Output format

All in one line , contain  N  It's an integer , Among them the first  i  The number represents the number  i  The first smaller number on the left of the number , If not, output  −1.

Data range

1≤N≤1e5
1≤ The elements in the sequence ≤1e9

sample input ：

5
3 4 2 7 5

sample output ：

-1 3 -1 2 2

Ideas

The first thing to think about is violence , Define a stack , Then start from the top of the stack every time to find a number smaller than the current element , Find it and output it directly , No output found -1, Finally, put the current element on the stack . The time complexity of violent practices is O(n²), subject N But 1e5,O(n²) The time complexity of will obviously time out , So we think about whether there is something that can be optimized .

Let's see if there is any nature , See if there are some elements in this stack that will never be output as answers . Take a chestnut , For example, we ask for the subscript 8 The first smaller number on the left of the number of , Here we use array to simulate stack , Define a stack a, Subscript to be 8 The previous numbers have all been put on the stack , We assume that a3>=a5, that a3 Will it never be output as an answer , Why? a3 It won't be output as an answer forever ？ because a5 stay a3 In front of , When we traverse the stack, we start from the top of the stack , The first traversal must be a5 instead of a3, Again because a3>=a5, therefore a3 Will never be output as an answer .

So we can find , If there is such a relationship in the stack ax>=ay And x<y Words ,ax It can be deleted , So the last sequence we have left must be a monotonic sequence , This is the monotone stack .

When the stack is monotonically increasing , At this time, a x, We need to find the first one in the stack x Small number . We start from the top of the stack ,x Wait, I want to enter the stack , If the stack top element is smaller than x Big words , because x To enter the stack , The top element of the stack will not be output , So the top of the stack should be deleted , Then traverse the stack in turn to find the ratio x Small numbers . If the stack top element is smaller than x Small words , Direct output , then x Into the stack .

Our code uses arrays to simulate stacks , Because it's faster and better .

The demo

Code implementation

#include <iostream>
using namespace std;
const int N=1e5+10;
int s[N];
int t;
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
       int x;
       cin>>x;
       // If x Smaller than the top element , Delete stack top element , Traverse the stack until you find the ratio x Small numbers 
       while(t&&s[t]>=x) t--;
       if(t) cout<<s[t]<<" ";// If not to the bottom of the stack 
       else cout<<"-1"<<" ";// If you get to the bottom of the stack 
       s[++t]=x;//x Into the stack 
    }
    return 0;
}