2019.12.18 七分糖~ 学习(单调栈,单调队列)
程序员文章站
2022-07-14 23:37:16
...
数组模拟单调栈:
代码:
/*
找到a[i]左边离i最近且比a[i]小
*/
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 100010;
int sta[N],tt;
int n;
int main(){
scanf("%d",&n);
int x;
for(int i = 0; i < n ;i++){
scanf("%d",&x);
while(tt && sta[tt] >= x) tt--;//找到左边极点
if(tt) printf("%d ",sta[tt]);
else printf("-1 ");
sta[++ tt] = x;
}
return 0;
}
数组模拟单调队列:
栗子:ACWing 154 滑动窗口
代码:
#include <iostream>
#include <cstdio>
using namespace std;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
const int N = 1000010;
int a[N], q[N];//数组,队列
int hh, tt;//定义队头,队尾
int n, k;
int main(){
scanf("%d%d",&n,&k);
FOR(i, 0, n) scanf("%d",&a[i]);
FOR(i, 0, n) {
if(hh <= tt && (i - k + 1) > q[hh]) hh ++;//判断队头是否出界
while(hh <= tt && a[i] <= a[q[tt]]) tt--;
q[ ++ tt] = i;
if(i >= k - 1) printf("%d ",a[q[hh]]);
}
printf("\n");
hh = 0, tt = 0;//初始化
FOR(i, 0, n) {
if(hh <= tt && (i - k + 1) > q[hh]) hh ++;//判断队头是否出界
while(hh <= tt && a[i] >= a[q[tt]]) tt--;
q[ ++ tt] = i;
if(i >= k - 1) printf("%d ",a[q[hh]]);
}
printf("\n");
return 0;
}