LeetCode 239. 滑动窗口最大值与单调队列

题目信息（题目链接）：

LeetCode 239. 滑动窗口最大值  题目要求：给定数组 nums 和窗口大小 k，窗口从左向右滑动，返回每一步窗口中最大值组成的数组。

面对这道题，第一反应是暴力解法：

// 暴力解法伪代码
for (int i = 0; i <= nums.size() – k; i++) {
int max_val = INT_MIN;
for (int j = i; j < i + k; j++) {
max_val = max(max_val, nums[j]); // 遍历窗口内 k 个元素找最大值
}
result.push_back(max_val);
}

时间复杂度：O(N * k)。 当数据量达到 10^5 级别时，计算量必然导致 Time Limit Exceeded (TLE)。我们急需一种能在 O(1) 时间内获取窗口最大值的数据结构。

思路演化：单调队列

如何优化？我们发现暴力解法中，很多元素被重复比较了。 假设窗口内有两个元素 nums[i] 和 nums[j]，且 i < j（i 在 j 左边），如果 nums[i] <= nums[j]，那么只要 nums[j] 还在窗口内，nums[i] 就永远不可能成为最大值。因为 nums[j] 比它大，且比它晚离开窗口。

基于这个观察，我们可以维护一个单调递减的队列：

队列里存放元素的下标。

队列头部的元素永远是当前窗口的最大值。

当新元素加入时，从队尾开始，把所有小于等于新元素的旧元素统统踢出队列

当窗口滑动时，检查队首元素是否过期（滑出窗口），过期则从队首移除。

这就是单调队列的核心思想：剔除了无用元素，使得获取最大值的时间复杂度降为 O(1)。

C++ std::deque 相关函数解析

在 C++ 中，实现单调队列的最佳容器是 std::deque（双端队列）。因为它允许我们在 O(1) 的时间内对两端进行操作。

结合本题，我们需要用到以下 4 个核心函数：

dq.back()：返回队尾元素的引用。

本题作用： 用于比较新元素与队尾元素的大小，判断是否需要剔除队尾。

dq.pop_back()：删除队尾元素。

本题作用： 当队尾元素小于等于新元素时，将其弹出，维持队列单调递减。

dq.front()：返回队首元素的引用。

本题作用： 获取当前窗口最大值的下标；同时检查队首下标是否过期。

dq.pop_front()：删除队首元素。

本题作用： 当队首元素滑出窗口（过期）时，将其弹出。

dq.push_back(i)：在队尾插入元素 i（下标）。

本题作用： 新元素入队。

代码：

下面是结合上述思路和 deque 函数的完整 C++ 代码，时间复杂度 O(N)，空间复杂度 O(k)。

class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
deque<int> dq; // 存储数组下标，对应 nums 的值单调递减

for (int i = 0; i < nums.size(); i++) {
// 1. 入队：维护单调递减
// 如果队尾元素 <= 当前元素，说明队尾永远无法成为最大值了，弹出
while (!dq.empty() && nums[dq.back()] <= nums[i]) {
dq.pop_back();
}
dq.push_back(i); // 当前元素下标入队

// 2. 出队：检查队首是否过期
// 窗口左边界是 i – k，如果队首下标 <= i – k，说明已经滑出窗口
if (dq.front() <= i – k) {
dq.pop_front();
}

// 3. 记录结果：当窗口长度达到 k 时（即 i >= k – 1）
if (i >= k – 1) {
result.push_back(nums[dq.front()]); // 队首就是当前窗口最大值
}
}
return result;
}
};

逐行拆解

以 nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 为例：

• i = 0 (val=1): 队列空，push_back(0)。dq = [0]。未满 k，不记录。

• i = 1 (val=3): nums[0]=1 <= 3，pop_back() 弹出 0。push_back(1)。dq = [1]。未满 k。

• i = 2 (val=-1): nums[1]=3 > -1，保留。push_back(2)。dq = [1, 2]。

  • 检查过期：front=1，i-k = 2-3 = -1。1 > -1，未过期。

  • i >= k-1 (2>=2)，记录 nums[front] = nums[1] = 3。结果: [3]

• i = 3 (val=-3): nums[2]=-1 > -3，保留。push_back(3)。dq = [1, 2, 3]。

  • 检查过期：front=1，i-k = 0。1 > 0，未过期。

  • 记录 nums[1] = 3。结果: [3, 3]

• i = 4 (val=5): nums[3]=-3 <= 5，弹出 3；nums[2]=-1 <= 5，弹出 2；nums[1]=3 <= 5，弹出 1。push_back(4)。dq = [4]。

  • 检查过期：front=4，i-k = 1。4 > 1，未过期。

  • 记录 nums[4] = 5。结果: [3, 3, 5]

• …以此类推，最终得到 [3, 3, 5, 5, 6, 7]。