当前位置：首页 > article >正文

leetcode239 滑动窗口最大值deque方式

article 2025/9/14 18:31:07

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

核心思路

问题分析：在滑动窗口中，若存在两个下标 i < j 且 nums[i] ≤ nums[j]，则 nums[i] 永远不可能成为后续窗口的最大值（因为 j 会比 i 更晚离开窗口）。因此，可以提前淘汰 nums[i]。
数据结构选择：使用双端队列（Deque）维护一个单调递减的下标序列，确保队列中元素对应的值从队首到队尾严格递减。
维护单调队列：
- 插入新元素：将新元素与队尾比较，若新元素更大，则不断弹出队尾，直到满足单调性。
- 淘汰旧元素：检查队首元素是否已超出窗口范围，若超出则弹出队首。

算法步骤

初始化队列：遍历前 k 个元素，维护单调队列。
处理每个窗口：
- 淘汰旧元素：若队首下标超出窗口左边界，弹出队首。
- 插入新元素：将当前元素下标加入队尾，弹出所有不大于当前值的队尾元素。
- 记录最大值：队首元素对应的值即为当前窗口的最大值。
滑动窗口：重复步骤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;
}