单调队列和单调栈

参考博客

单调队列例题

  • 洛谷P1886 滑动窗口 : https://www.luogu.org/problem/P1886
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    #include <bits/stdc++.h>
    using namespace std;
    struct node
    {
    int val;
    int index;
    };
    int a[1000005];
    int main()
    {
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    deque<node> q;
    //维护单调递增
    for(int i = 1; i <= n; i++){
    while(q.size() && q.front().index <= (i - k))
    q.pop_front();
    while(q.size() && q.back().val >= a[i])
    q.pop_back();
    q.push_back(node{a[i], i});
    if(i >= k) cout << q.front().val << " ";
    }
    while(q.size()) q.pop_front();
    cout << endl;
    //维护单调递减
    for(int i = 1; i <= n; i++){
    while(q.size() && q.front().index <= (i - k))
    q.pop_front();
    while(q.size() && q.back().val <= a[i])
    q.pop_back();
    q.push_back(node{a[i], i});
    if(i >= k) cout << q.front().val << " ";
    }
    return 0;
    }
  • 洛谷P12032 扫描 : https://www.luogu.org/problem/P2032
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    #include <bits/stdc++.h>
    using namespace std;
    struct node
    {
    int val;
    int index;
    };
    int a[2000005];
    int main()
    {
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    deque<node> q;
    //维护单调递减
    for(int i = 1; i <= n; i++){
    while(q.size() && q.front().index <= (i - k))
    q.pop_front();
    while(q.size() && q.back().val <= a[i])
    q.pop_back();
    q.push_back(node{a[i], i});
    if(i >= k) cout << q.front().val << endl;
    }
    return 0;
    }

本文标题:单调队列和单调栈

文章作者:HKer_YM

发布时间:2019年09月02日 - 22:55:16

最后更新:2020年03月01日 - 12:26:46

原始链接:https://blog.dreams-wj.top/2019/09/02/%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97%E5%92%8C%E5%8D%95%E8%B0%83%E6%A0%88/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。