问题

单调队列在查找最值时，时间复杂度是多少？

单调栈、单调队列的思维

考虑朴素的模拟，然后优化删去过程中的无效数据，如果剩下的数据有单调性，就可以接着进行某些操作。

单调队列在多重背包Ⅲ中有应用。

#include<iostream>

#define _rep_le(i, a, b) for(int i = (a); i <= (b); ++ i)
#define _rep_lt(i, a, b) for(int i = (a); i < (b); ++ i)
#define _rep_ge(i, a, b) for(int i = (b); i >= (a); -- i)
#define _rep_gt(i, a, b) for(int i = (b); i > (a); -- i)

using namespace std;

const int N = 1e6 + 5;

int arr[N], que[N];
int que_h = 0, que_t = -1;

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

    int n = 0, len = 0;
    cin >> n >> len;

    _rep_lt(i, 0, n) {
        cin >> arr[i];
    }

    //slide window's min
    _rep_lt(i, 0, n) {
        // check head
        if(que_h <= que_t && que[que_h] < i - len + 1) que_h ++;
        // insert arr[i]
        while(que_h <= que_t && arr[que[que_t]] >= arr[i]) que_t --;
        // replace que_t && "i" insert in
        // ***** 后进入的值直接替换掉前面进入的大于等于 arr[i] 的值是可以保证队列的正确性的
        que_t ++;
        que[que_t] = i;
        // output current min
        if(i >= len - 1) cout << arr[que[que_h]] << " ";
    }
    cout << endl;
    // init queue
    que_h = 0, que_t = -1;
    // slide window's max
    _rep_lt(i, 0, n) {
        if(que_h <= que_t && que[que_h] < i - len + 1) que_h ++;
        while(que_h <= que_t && arr[que[que_t]] <= arr[i]) que_t --;
        que_t ++;
        que[que_t] = i;
        if(i >= len - 1) cout << arr[que[que_h]] << " ";
    }

    return 0;
}