1.单调栈
题目
给定某个数列，找到每个数左边第一个比它小的数
样例
输入样例：
5 3 4 2 7 5
输出样例：
-1 3 -1 2 2
思路
性质：如果数列栈中存在这样的关系，ax>=ay且x<y那么，ax肯定不会作为答案被输出，那么ax就可以被删除
用单调递增栈，当该元素可以入栈的时候，栈顶元素就是它左侧第一个比它小的元素。
代码
#include <bits/stdc++.h> using namespace std; const int N = 100010; int tt; int skt[N]; int main() { int n; cin>>n; while(n--) { int a; scanf("%d",&a); while(tt && skt[tt]>=a) tt--; if(!tt) printf("-1 "); else printf("%d ",skt[tt]); skt[++tt]=a; } return 0; }
2.滑动窗口（单调队列）
题目
输入输出数据范围
样例
输入样例：
8 3 1 3 -1 -3 5 3 6 7
输出样例：
-1 -3 -3 -3 3 3 3 3 5 5 6 7
思路
寻找单调性，拿寻找滑动窗口队列中最小值为例，当一个窗口中出现，ai>=ak且k>i时（不是单调递增），那么ai就是一个无用元素，可以进行删除，以此来维护每个队列的单调递增状态
在单调递增的队列中，队头元素就是当前窗口的最小元素
求最大值，对称来做即可
代码
#include <bits/stdc++.h> using namespace std; const int N = 1000010; int a[N],q[N]; int n,k; int main() { cin>>n>>k; int hh=0,tt=-1; for(int i=0;i<n;i++) { scanf("%d",&a[i]); if(i-k+1>q[hh]) ++hh; // 解决队首出队问题 while(hh<=tt && a[i]<=a[q[tt]]) --tt; // 排除无用元素 q[++tt]=i; if(i+1>=k) printf("%d ",a[q[hh]]); } cout<<endl; hh=0,tt=-1; for(int i=0;i<n;i++) { if(i-k+1>q[hh]) ++hh; // 解决队首出队问题 while(hh<=tt && a[i]>=a[q[tt]]) --tt; // 排除无用元素 q[++tt]=i; if(i+1>=k) printf("%d ",a[q[hh]]); } return 0; }
