返回题解分享
讨论 / 题解分享/ 帖子详情

单调队列 - 题解

单调队列板子

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int a[N];
int n;
deque<int> q;
int main(){
    scanf("%d",&n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a[i]);
    }
    for (int i = 1; i <= n; ++i) {
        while(!q.empty() && a[q.back()] <= a[i]) q.pop_back();
        q.push_back(i);
    }
    for (int i = 0; i <= q.size() - 1; ++i) {
        printf("%d ",a[q[i]]);
    }
    return 0;
}
0 回复 0 转发 0 喜欢 2 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!