欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}
相关标签: 基础 基础算法