NO.77十六届蓝桥杯备战|数据结构-单调队列|质量检测(C++)

1. 什么是单调队列？
   单调队列，顾名思义，就是存储的元素要么单调递增要么单调递减的队列。注意，这⾥的队列和普通的队列不⼀样，是⼀个双端队列。
2. 单调队列解决的问题
   ⼀般⽤于解决滑动窗⼝内最⼤值最⼩值问题，以及优化动态规划

P1886 滑动窗口 /【模板】单调队列 - 洛谷

窗⼝内最⼤值：
从左往右遍历元素，维护⼀个单调递减的队列：

• 当前元素进队之后，注意维护队列内的元素在⼤⼩为k的窗⼝内；
• 此时队头元素就是最⼤值。
  窗⼝内最⼩值：
  从左往右遍历元素，维护⼀个单调递增的队列：
• 当前元素进队之后，注意维护队列内的元素在⼤⼩为k的窗⼝内；
• 此时队头元素就是最⼩值

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

const int N = 1e6 + 10;

int n, k;
int a[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    deque<int> q; //存下标
    //最小值，递增队列
    for (int i = 1; i <= n; i++)
    {
        while (q.size() && a[q.back()] >= a[i]) q.pop_back();

        q.push_back(i);

        //判断队列元素是否合法
        if (q.back() - q.front() + 1 > k) q.pop_front();
        
        if (i >= k) cout << a[q.front()] << " ";
    }
    cout << endl;

    //最大值，递减队列
    q.clear();
    for (int i = 1; i <= n; i++)
    {
        while (q.size() && a[q.back()] <= a[i]) q.pop_back();

        q.push_back(i);

        //判断队列元素是否合法
        if (q.back() - q.front() + 1 > k) q.pop_front();
        if (i >= k) cout << a[q.front()] << " ";
    }
    cout << endl;
    
    return 0;
}

P2251 质量检测 - 洛谷

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

const int N = 1e6 + 10;

int n, m;
int a[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    deque<int> q;
    for (int i = 1; i <= n; i++) 
    {
        cin >> a[i];
        while (q.size() && a[q.back()] >= a[i]) q.pop_back();

        q.push_back(i);
        
        if (q.back() - q.front() + 1 > m) q.pop_front();

        if (i >= m) cout << a[q.front()] << endl;
    }

    return 0;
}