单调栈&单调队列

啊学完了来写个总结吧


概念解释:

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


单调栈:

单调栈模板

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

我做了两种做法,一个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的会快很多,考场上遇到单调栈/队列尽量手写吧。

原文链接: https://www.cnblogs.com/bzzs/p/13084515.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬

    单调栈&单调队列

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/354230

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年3月2日 上午8:28
下一篇 2023年3月2日 上午8:29

相关推荐