单调队列和单调栈
单调队列
应用：滑动窗口中的最大（最小值）
例：给定一个数列$a$，窗口的长度$k$，求滑动窗口的最小值和最大值
分析：以最大值为例：用队列存储当前窗口的值，保证队头是最大值，每次滑动窗口时先判断队头是否过期，若过期，则弹出队头，然后从队尾开始把小于等于当前数的数删除(当前数后出队，比它大，则一定不会取它),在插入当前数。为了方便判断过期，队列中存储的是下标。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,k;
int a[N];
int q[N],hh,tt=-1;
int main(){
cin >> n >> k;
for(int i=1;i<=n;i++){
cin >> a[i];
}
for(int i=1;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)cout << a[q[hh]] << ' ';
}
cout << endl;
hh=0,tt=-1;
for(int i=1;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)cout << a[q[hh]] << ' ';
}
}
|
单调栈
应用：求出每个数左边第一个比它小的数
分析：先考虑朴素做法：
1
2
3
4
5
6
7
8
| for(int i=1;i<=n;i++){
for(int j=i-1;j>=1;j--){
if(s[j]<s[i]){
cout << s[j] << ' ';
break;
}
}
}
|
通过分析可以发现，如果$a[i]\ge aj$，那么$a[i]$永远不会是右边的数的答案，所以利用栈，每次插入时把所有大于等于当前数的数弹出，直到队列为空时或栈顶小于当前数时为止，这样就能快速求出每个数左边第一个比它小的数。可以发现，这样形成的栈具有单调性，被称为单调栈。
代码实现：
1
2
3
4
5
6
7
8
| for(int i=1;i<=n;i++){
int tmp;
cin >> tmp;
while(tt&&stk[tt]>=tmp)tt--;
if(tt)cout << stk[tt] << ' ';
else cout << -1 << ' ';
stk[++tt]=tmp;
}
|