单调栈

单调栈和单调队列通常的做法，用栈或者队列来存储元素，用栈和队列来考虑暴力的模拟方法，然后观察栈和队列里面的元素，看看是否有一些元素完全没用，把这些元素删掉，看看剩余元素是否有单调性，有单调性就可以看看题义，做出来了。

单调栈：

求一个数列中比第i个数小且最近的数

 原数组a[i]                                                                    3  4   2  7  5

第i个比a[i]小且最近的的数（从第i个数开始往左数） -1  3  -1  2  2

1. #include <iostream>  
2. using namespace std;  
3. const int N=10010;  
4. int n;  
5. int stk[N],tt;  
6. int main()  
7. {  
8.     ios_base::sync_with_stdio(0);  
9.     cin.tie(0);  
10.     cout.tie(0);  
11.     cin>>n;  
12.     for(int i=0;i<n;i++){  
13.         int x;  
14.         cin>>x;  
15.         while(tt&&stk[tt]>=x)tt--;  
16.         if(tt)cout<<stk[tt]<<" ";  
17.         else cout<<-1<<" ";  
18.         stk[++tt]=x;  
19.     }  
20.     return 0;  
21.  }   

单调队列：

acwing 滑动窗口

154. 滑动窗口 - AcWing题库

1. #include <iostream>  
2. using namespace std;  
3. const int N=1000010;  
4. int n,k;  
5. int a[N],q[N];  
6. int main()  
7. {  
8.     scanf("%d%d",&n,&k);  
9.     for(int i=0;i<n;i++)scanf("%d",&a[i]);  
10.     int hh=0,tt=-1;  
11.     for(int i=0;i<n;i++){  
12.         //hh<=tt队列不为空，负责队列为空   
13.         //判断队头是否已经滑出窗口  
14.         if(hh<=tt&&i-k+1>q[hh])hh++;  
15.         //判断新加的数是否会让前面的数删除  
16.         while(hh<=tt&&a[q[tt]]>=a[i]) tt--;  
17.         q[++tt]=i;  
18.         //当不够k个数的话不输出，够了k个数才输出   
19.         if(i>=k-1)printf("%d ",a[q[hh]]);  
20.     }  
21.     puts(" ");  
22.     hh=0,tt=-1;  
23.     for(int i=0;i<n;i++){  
24.         //hh<=tt队列不为空，负责队列为空   
25.         //判断队头是否已经滑出窗口  
26.         if(hh<=tt&&i-k+1>q[hh])hh++;  
27.         //判断新加的数是否会让前面的数删除  
28.         while(hh<=tt&&a[q[tt]]<=a[i]) tt--;  
29.         q[++tt]=i;  
30.         //当不够k个数的话不输出，够了k个数才输出   
31.         if(i>=k-1)printf("%d ",a[q[hh]]);  
32.     }  
33.     puts(" ");  
34.     return 0;  
35. }