单调栈 —— 模板题 AcWing 830. 单调栈
常见模型:找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (tt && check(stk[tt], i)) tt -- ;
stk[ ++ tt] = i;
}
单调队列 —— 模板题 AcWing 154. 滑动窗口
常见模型:找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口
while (hh <= tt && check(q[tt], i)) tt -- ;
q[ ++ tt] = i;
}
具体题例
#include<bits/stdc++.h>
using namespace std;
const int n = 111111;
int stk[n],t=0;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int m;cin>>m;
int x;
for(int i = 0;i < m; i++)
{
cin>>x;
while(t&&stk[t]>=x)t--;
if(t)cout<<stk[t]<<' ';
else cout<<-1<<' ';
stk[++t]=x;
}
}
//////////////////////////////////////////////
#include<bits/stdc++.h>
using namespace std;
const int n = 1111111;
int q[n],a[n],h=0,t=-1;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int m,k;
cin>>m>>k;
for(int i = 0;i < m;i++)
{
cin>>a[i];
if(i-k+1>q[h])h++;
while(t>=h&&a[i]<=a[q[t]])t--;
q[++t]=i;
if(i+1>=k)cout<<a[q[h]]<<' ';
}
cout<<endl;
h=0,t=-1;
for(int i= 0;i<m;i++)
{
if(i-k+1>q[h])h++;
while(t>=h&&a[i]>=a[q[t]])t--;
q[++t]=i;
if(i+1>=k)cout<<a[q[h]]<<' ';
}
}