Stack and queue

Monotonic stack

Title Description ：

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 ≤ 10^5

1 ≤ The elements in the sequence ≤ 10^9

sample input ：

5

3 4 2 7 5

sample output ：

-1 3 -1 2 2

Their thinking ：

If you follow the most simple idea —— Violent settlement , So I have to write two for loop , Find No i The number nearest to it and smaller than itself .

Of course not hard to find , If in front of i In number , There are two numbers respectively x and y,x>y, also y The position is in x Behind , Then we just need to use y With the first i Just compare the numbers . therefore , We can judge when we input , If the number entered is larger than the top of the stack , Then the number at the top of the stack is output ; If the number entered is smaller than the number at the top of the stack , Then it becomes the new top of the stack , And the output -1.

such , Each number only needs to be put on the stack at most 、 Once out of the stack . The code is as follows ：

#include<iostream>
using namespace std;

const int N=100010;
int n;
int stk[N],tt;//stk[] For the stack ,tt For the top of the stack  

int main(){
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		while(tt&&stk[tt]>=x)tt--;//tt Not empty   And  x Delete the top of the stack when it is less than or equal to the number at the top of the stack  
		if(tt)cout<<stk[tt]<<' ';// If the stack is not empty, the top of the stack is output  
		else cout<<-1<<' ';// Otherwise output -1 
		
		stk[++tt]=x;// Input x For the top of the stack  
	}
	return 0;
}

Another template question

Luogu P5788 【 Templates 】 Monotonic stack

Input  

5
1 4 2 3 5

Output  

2 5 4 5 0

explain / Tips

【 Data scale and agreement 】

about  30\%30%  The data of ,n ≤ 100;

about  60\%60%  The data of ,n ≤ 5 × 10^3;

about  100\%100%  The data of ,1 ≤ n ≤ 3 × 10^6,1 ≤ ai ≤ 10^9.

The same idea as the question just now . The code is as follows ：

#include<iostream>
using namespace std;
const int N=3e6+10;
int a[N],stk[N],ans[N];//a[] For input value ,stk[] For the stack ,ans[] Record subscripts  
int tt=0;//tt For the top of the stack  
int n,i;

int main(){
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>a[i];
	}
	for(i=1;i<=n;i++){
		while(tt&&a[stk[tt]]<a[i])ans[stk[tt--]]=i;
        // If the top of the stack is not empty , And the value corresponding to the top element of the stack is higher than the newly entered value a[i] Small , Delete the top of the stack , And record a[i] The subscript i 
		stk[++tt]=i;// here i For the stack top element    
	}
	for(i=1;i<=n;i++){
		if(i==1)cout<<ans[i];
		else cout<<" "<<ans[i];
	}
	return 0;
}

Of monotonic queues classic Water problem The template questions   P1886 The sliding window  

Title Description

There's a long one for  n  Sequence  a, And a size of  k  The window of . Now this one slides from the left to the right , Slide one unit at a time , Find the maximum and minimum values in the window after each slide .

for example ：

The array is [1,3,−1,−3,5,3,6,7], and k = 3.

Input format

There are two lines of input , The first line has two positive integers  n,k. The second line  n  It's an integer , Represents a sequence  a

Output format

The output consists of two lines , The first line is the minimum value of each window slide
The second line is the maximum value of each window sliding

Input  

8 3
1 3 -1 -3 5 3 6 7

Output  

-1 -3 -3 -3 3 3
3 3 5 5 6 7

explain / Tips

【 Data range 】
about 50%  The data of ,1 ≤ n ≤ 10^5;
about 100%  The data of ,1 ≤ k ≤ n ≤ 10^6,ai∈[-2^31,2^31).

Their thinking ：

If you follow the idea of violence , Every k The number is searched once , Find the smallest （ Maximum ） Output .

But we can record this k The smallest number （ Maximum ） Number of numbers , Compare with the next number . If the next number is smaller , Then output the next number and write it into the queue ; conversely , Is to output the original minimum value . The code is as follows ：

#include <iostream>
using namespace std;
const int N = 1000010;
int a[N], q[N];//a[] Is the original array ;q[] For queue , Indicates subscript 

int main(){
    int n, k;
    cin>>n>>k;
    for (int i = 0; i < n; i ++ ) cin>>a[i];

    int hh = 0, tt = -1;//hh For the team leader ;tt For the end of the team  
    for (int i = 0; i < n; i ++ )
    {
        if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;
        // Pop up the team leader  
        while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;
        // If the next number is smaller than the number at the end of the team , Then replace the end of the queue with the next number  
        q[ ++ tt] = i;

        if (i >= k - 1) cout<<a[q[hh]]<<" ";
        // Output team leader  
    }
    puts("");

// Maximum   Empathy 
    hh = 0, tt = -1;
    for (int i = 0; i < n; i ++ )
    {
        if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;
        while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
        q[ ++ tt] = i;

        if (i >= k - 1) cout<<a[q[hh]]<<" ";
    }
    puts("");

    return 0;
}