leetcode239 滑动窗口最大值deque方式

这段文字描述的是使用单调队列（Monotonic Queue） 解决滑动窗口最大值问题的优化算法。我来简单解释一下：

核心思路

1. 问题分析：在滑动窗口中，若存在两个下标 i < j 且 nums[i] ≤ nums[j]，则 nums[i] 永远不可能成为后续窗口的最大值（因为 j 会比 i 更晚离开窗口）。因此，可以提前淘汰 nums[i]。

2. 数据结构选择：使用双端队列（Deque）维护一个单调递减的下标序列，确保队列中元素对应的值从队首到队尾严格递减。

3. 维护单调队列：

   • 插入新元素：将新元素与队尾比较，若新元素更大，则不断弹出队尾，直到满足单调性。
   • 淘汰旧元素：检查队首元素是否已超出窗口范围，若超出则弹出队首。

算法步骤

1. 初始化队列：遍历前 k 个元素，维护单调队列。
2. 处理每个窗口：
   • 淘汰旧元素：若队首下标超出窗口左边界，弹出队首。
   • 插入新元素：将当前元素下标加入队尾，弹出所有不大于当前值的队尾元素。
   • 记录最大值：队首元素对应的值即为当前窗口的最大值。
3. 滑动窗口：重复步骤2，直到处理完所有窗口。

示例代码（C++）

#include <iostream>
#include <vector>
#include <deque>
using namespace std;vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();vector<int> result;if (n == 0 || k == 0) return result;deque<int> q; // 存储下标，对应的值单调递减// 初始化第一个窗口（前k个元素）for (int i = 0; i < k; ++i) {// 弹出所有比当前元素小的队尾下标（维护单调递减）while (!q.empty() && nums[i] >= nums[q.back()]) {q.pop_back();}q.push_back(i);}result.push_back(nums[q.front()]); // 第一个窗口的最大值// 滑动窗口处理后续元素for (int i = k; i < n; ++i) {// 淘汰已离开窗口的队首下标（左边界为i-k+1，下标<=i-k时淘汰）while (!q.empty() && q.front() <= i - k) {q.pop_front();}// 维护单调递减：弹出所有比当前元素小的队尾下标while (!q.empty() && nums[i] >= nums[q.back()]) {q.pop_back();}q.push_back(i);result.push_back(nums[q.front()]); // 当前窗口最大值}return result;
}// 测试示例
int main() {vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};int k = 3;vector<int> res = maxSlidingWindow(nums, k);cout << "滑动窗口最大值：";for (int num : res) {cout << num << " ";}// 输出：3 3 5 5 6 7return 0;
}

复杂度分析

• 时间复杂度：O(n)，每个元素最多入队和出队一次。
• 空间复杂度：O(k)，队列中最多存储 k 个元素。

关键点

• 单调队列：通过维护单调性，避免重复比较，将暴力算法的 O(nk) 优化到 O(n)。
• 双端队列：支持 O(1) 时间复杂度的队首和队尾操作。
• 应用场景：适用于求解滑动窗口最大值/最小值、子数组最大和等问题。