单调栈&单调队列

啊学完了来写个总结吧

概念解释：

顾名思义，单调，就是指色彩单一某一个容器里面的元素都是递增或递减的，而单调栈和单调队列就是这个容器。

单调栈：

单调栈模板

其他的我就不说了，讲下为什么单调栈是从后往前扫描： 当我们在判断一个数后面第一个比它大的数时，前提是后面的数已经被处理了，所以我们要从后往前扫描。

我做了两种做法，一个STL的，一个手写的。

STL：

#include <bits/stdc++.h>
using namespace std;
int n;
int ans[3000010] , a[3000010];
stack<int> q; 
inline int read(){
    int x(0);
    char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48) , c = getchar();
    return x;
}
int main(){
    n = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    for(int i = n; i >= 1; i--){
        while(!q.empty() && a[i] >= a[q.top()]) q.pop();
        if(q.empty()) ans[i] = 0;
        else ans[i] = q.top();
        q.push(i);
    }
    for(int i = 1; i <= n; i++) printf("%d " , ans[i]);
    return 0;
}

手写：

#include <bits/stdc++.h>
using namespace std;
int n , t = 0;
int ans[3000010] , a[3000010] , s[3000010];
stack<int> q; 
inline int read(){
    int x(0);
    char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48) , c = getchar();
    return x;
}
int main(){
    n = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    for(int i = n; i >= 1; i--){
        while(t > 0 && a[i] >= a[s[t]]) t--;
        if(t == 0) ans[i] = 0;
        else ans[i] = s[t];
        s[++t] = i;
    }
    for(int i = 1; i <= n; i++) printf("%d " , ans[i]);
    return 0;
}

提醒：这道题不用快读会超时的。

单调队列

单调队列模板

直接看代码吧没啥好讲的很好理解的qwq（只有手写哒，如想用STL，需要使用STL里面的双端队列哦）。

code：

#include <bits/stdc++.h>
using namespace std;
int n , k;
int a[1000010] , q[2000010];
int s = 1 , e = 0;
int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++){
        if(i > k) cout << a[q[s]] << " ";
        if(i - q[s] + 1 > k && s <= e) s++;
        while(a[i] < a[q[e]] && s <= e) e--;
        q[++e] = i;
    }
    cout << a[q[s]] << endl;
    s = 1 , e = 0;
    for(int i = 1; i <= n; i++){
        if(i > k) cout << a[q[s]] << " ";
        if(i - q[s] + 1 > k && s <= e) s++;
        while(a[i] > a[q[e]] && s <= e) e--;
        q[++e] = i; 
    }
    cout << a[q[s]] << endl;
    return 0;
}

最后提醒一句，手写的比STL的会快很多，考场上遇到单调栈/队列尽量手写吧。