论单调栈和单调队列的小彩笔同学的总结

youhualiuh / 2024-04-18 / 原文

单调队列

洛谷传送阵：https://www.luogu.com.cn/problem/P1886

题意描述:

有一个长度为n的数组a, 已经一个长度为k的窗口,从左往右滑动窗口求出滑动窗口后的最大值和最小值.第一行是最小值，第二行为最大值。题意简单明了，请看操作。

1-暴力

最简单有朴实无华,从头到尾我扫一遍检查k的元素检查nk次很明显这题会TLE，让我朴实无华的小手无处安放.可恶.我们就使用单调队列进行O(n)的操作来实现它。

讲了许久也没讲出单调队列是啥玩意。那么你先别急,它来了.

2-单调队列

1-队头是最小的,根据需求输出队头,但是不一定要弹出.

2-队尾进入队列,从队头队尾都可以弹出.

3-序列每一个元素都需要进入队列比较.

想到这里,我脑子想着老子的 STL 大法deque 它来了.

#include<bits/stdc++.h>
    
using namespace std; 

const int N = 1e6 + 5;

int a[N], n, k;

deque <int> q;

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];   
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && a[q.back()] > a[i]) q.pop_back();
        q.push_back(i);
        if (i >= k) {
            while (!q.empty() && q.front() <= i - k) q.pop_front();
            cout << a[q.front()] << ' ';
        }
    }
    cout << '\n';
    while (!q.empty()) q.pop_back();
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && a[q.back()] < a[i]) q.pop_back();
        q.push_back(i);
        if (i >= k) {
            while (!q.empty() && q.front() <= i - k) q.pop_front();
            cout << a[q.front()] << ' ';
        }
    }
    return 0;
}