549 字
3 分钟
Problem: Sliding Window Maximum (LeetCode 239)

Problem: Sliding Window Maximum (LeetCode 239)#

题目重述#

给定整数数组 nums\text{nums} 与正整数 kk,输出每个长度为 kk 的滑动窗口中的最大值。

  • 输入:nums=[1,3,−1,−3,5,3,6,7]\text{nums} = [1, 3, -1, -3, 5, 3, 6, 7],k=3k = 3
  • 输出:[3,3,5,5,6,7][3, 3, 5, 5, 6, 7]
  • 约束:1≤k≤∣nums∣≤1051 \le k \le |\text{nums}| \le 10^5

关键观察#

若窗口内存在下标 i<ji < j 且 nums[i]≤nums[j]\text{nums}[i] \le \text{nums}[j],则只要 jj 仍在窗口中,nums[i]\text{nums}[i] 就不可能成为最大值。因此可用单调递减双端队列维护可能成为最大值的元素下标:遇到更大元素时从尾部弹出较小元素,窗口左边界滑动时从头部弹出过期下标。队列值严格递减,队首即为当前窗口最大值。

解析#

遍历下标 ii,维护双端队列 dq\text{dq}:

  1. 若 dq.front()<i−k+1\text{dq.front}() < i - k + 1,则 pop_front()\text{pop\_front}()。
  2. 当队列非空且 nums[dq.back()]≤nums[i]\text{nums}[\text{dq.back}()] \le \text{nums}[i] 时,持续 pop_back()\text{pop\_back}()。
  3. 将 ii 入队。
  4. 若 i≥k−1i \ge k - 1,将 nums[dq.front()]\text{nums}[\text{dq.front}()] 加入答案。

以 nums=[1,3,−1,−3,5,3,6,7]\text{nums} = [1, 3, -1, -3, 5, 3, 6, 7]、k=3k = 3 为例:

首个窗口 [1,3,−1][1, 3, -1] 建立时,下标 00 入队;下标 11 的值 33 大于 11,弹出 00 后入队;下标 22 的值 −1-1 直接入队。此时队列为 [1,2][1, 2],对应值 [3,−1][3, -1],窗口最大值为 33。

步骤 1:首个窗口建立,维护单调递减队列

当 i=4i = 4、值为 55 的元素进入时,55 大于队列中所有元素,依次弹出 2,32, 3 后只剩 [4][4],窗口最大值更新为 55。

步骤 2:新元素 5 破坏单调性,弹出所有较小元素

最终窗口到达数组末尾,队首下标 77 对应值 77,窗口最大值为 77。

步骤 3:最终窗口,队首始终为当前最大值

复杂度分析:每个下标最多入队一次、出队一次,时间复杂度为 O(n)O(n);队列最多保存 kk 个下标,空间复杂度为 O(k)O(k)。

代码#

class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq;
vector<int> res;
for (int i = 0; i < nums.size(); ++i) {
if (!dq.empty() && dq.front() < i - k + 1) dq.pop_front();
while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
dq.push_back(i);
if (i >= k - 1) res.push_back(nums[dq.front()]);
}
return res;
}
};
Problem: Sliding Window Maximum (LeetCode 239)
https://sanzenin.top/posts/obsidian/problem-sliding-window-maximum/
作者
Sanzenin 凪
发布于
2026-11-16
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取