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

Problem: Sliding Window Maximum (LeetCode 239)
题目重述
给定整数数组 与正整数 ,输出每个长度为 的滑动窗口中的最大值。
- 输入:,
- 输出:
- 约束:
关键观察
若窗口内存在下标 且 ,则只要 仍在窗口中, 就不可能成为最大值。因此可用单调递减双端队列维护可能成为最大值的元素下标:遇到更大元素时从尾部弹出较小元素,窗口左边界滑动时从头部弹出过期下标。队列值严格递减,队首即为当前窗口最大值。
解析
遍历下标 ,维护双端队列 :
- 若 ,则 。
- 当队列非空且 时,持续 。
- 将 入队。
- 若 ,将 加入答案。
以 、 为例:
首个窗口 建立时,下标 入队;下标 的值 大于 ,弹出 后入队;下标 的值 直接入队。此时队列为 ,对应值 ,窗口最大值为 。

当 、值为 的元素进入时, 大于队列中所有元素,依次弹出 后只剩 ,窗口最大值更新为 。

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

复杂度分析:每个下标最多入队一次、出队一次,时间复杂度为 ;队列最多保存 个下标,空间复杂度为 。
代码
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/分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 0 天
部分内容可能已过时