单调队列(Monotonic Queue)

组别：提高级
难度：5

单调队列是队列中的元素始终保持着单增或者单减的特性。单调队列不只是做到了排序，还可以实现一个功能：在每次加入或者删除元素时都保持序列里的元素有序，即队首元素始终是最小值或者最大值，这个功能非常重要，单调队列我们就是使用的这个功能。

举个例子：我们依次加入5个元素，分别为5，8，2，4，1
那么我们假设队列是单减的，那么队首元素始终是最大的，五次操作后的队列元素排列情况如下：

1: 5
2: 8
3: 8 2
4: 8 4
5: 8 4 1
详细过程如下：
1.首先队列里面没有元素，5加进去。
2.第二个元素8大于队尾的元素，所以5要弹出去，8加进去。保持队首最大
3.第三个元素2小于队尾元素8，可以加进去，变为8 2
4.4大于队尾元素2，2弹出，4小于8，8不弹出，4加进去
5.1小于队尾元素4，1加进去，最后队列为8 4 1

#include <iostream>
#include <deque>

using namespace std;

int main() {
    deque<int> dq;
    vector<int> nums = {3, 1, 5, 2};

    for (int i = 0; i < nums.size(); ++i) {
        // 移除比当前元素小的元素
        while (!dq.empty() && dq.back() < nums[i]) {
            dq.pop_back();
        }
        // 插入当前元素
        dq.push_back(nums[i]);
    }

    // 打印单调队列（递减顺序）
    cout << "单调递减队列：" << endl;
    for (int x : dq) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

问题描述

给定一个大小为 n的数组和一个滑动窗口大小 k，要求计算每个滑动窗口中的最大值。

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

// 单调队列实现滑动窗口最大值
vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
    deque<int> dq; // 双端队列，存储数组的下标，维护单调递减
    vector<int> result; // 存储结果

    for (int i = 0; i < nums.size(); ++i) {
        // 1. 移除不在窗口范围内的元素（从队头移除过期元素）
        if (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }

        // 2. 移除队列中比当前元素小的元素（保持队列单调递减）
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }

        // 3. 将当前元素的下标加入队列
        dq.push_back(i);

        // 4. 记录当前窗口的最大值（从队头获取最大值）
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }

    return result;
}

// 主函数：测试代码
int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;

    vector<int> result = maxSlidingWindow(nums, k);

    cout << "滑动窗口的最大值为：";
    for (int val : result) {
        cout << val << " ";
    }

    return 0;
}

Previous Topic

Back to Lesson

Next Quiz

数据结构与算法

单调队列(Monotonic Queue)

问题描述