题目描述

什么是单调队列：队列内元素的值是单调的

ACWING 154 滑动窗口

有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边，找出每次滑动窗口的最小值和最大值

模板

常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

时间复杂度

同单调栈，每一个元素只会进队列一次，出栈一次（虽然是一层for套着一层while），所以是O(n)

代码注意点

• windowLength = 1 的边界情况
• 利用record[N]记录队列里每一个元素在原array的下标，辅助以判断队头是否滑出窗口

我的代码

# include <iostream>

using namespace std;
const int N = 1e6 + 10;



int main() {
    int array[N];
    int queue[N], head = 0, tail = 0, record[N] = { -1 };
    //int queue[N], head = 0, tail = 0, record[N] = { -1 };
    int arrayLength, windowLength;

    cin >> arrayLength >> windowLength;
    for (int i = 0; i < arrayLength; i++) {
        cin >> array[i];
    }

    for (int i = 0; i < arrayLength; i++) {
        /*
        当windowLength == 1时，array[0]只插入，不输出窗口中的最值，是有问题的。
        因此，为了应对这种特殊情况，多加一个判断：tail - head >= 0（但我还是不知道多了这个判断有什么用）
        if (i == 0) { 
            queue[++tail] = array[i];// num队尾入队
            record[tail] = i;
            continue;
        }
        */

        // 维护单调递增的队列
        while (tail - head >= 0 && tail >= 0 && array[i] <= queue[tail]) { // 队列不为空
            tail--;
        }
        queue[++tail] = array[i];// num队尾入队
        record[tail] = i;
        // 维护队头，要保证队里面的元素都在window里，且不缺不漏
        // 每次只将1个Num入队，因此，最多head++ 1次
        if (record[head] <= i - windowLength) {
            head++;
        }
        if (i + 1 >= windowLength) {
            //resultMin[idx] = queue[head];
            cout << queue[head] << ' ';// 输出此位置的滑动窗口的min
        }
    }
    cout << endl;
    head = 0;
    tail = 0;
    for (int i = 0; i < arrayLength; i++) {
        /*
        if (i == 0) {
            queue[++tail] = array[i];// num队尾入队
            record[tail] = i;
            continue;
        }
        */
        // 维护单调递减的队列
        while (tail - head >= 0 && tail >= 0 && array[i] >= queue[tail]) {
            tail--;
        }
        queue[++tail] = array[i];// num队尾入队
        record[tail] = i;
        // 维护队头，要保证队里面的元素都在window里，且不缺不漏
        if (record[head] <= i - windowLength) {
            head++;
        }
        if (i + 1 >= windowLength) {
            //resultMax[++idx] = queue[head];
            cout << queue[head] << ' ';// 输出此位置的滑动窗口的min
        }
    }
    return 0;
}