0239. Sliding Window Maximum
============================
题目信息
--------
:题号: 0239
:难度: Hard
:主题: 数组、滑动窗口、单调队列
:原题: `LeetCode 0239 `_
:重点: 固定长度连续窗口、每次右移一格、按窗口起点返回最大值、重复最大值
题目重述
--------
给定整数数组 ``nums`` 和窗口长度 ``k``。一个长度恰好为 ``k`` 的连续窗口从数组最左端开始,每次向右移动一个位置,直到覆盖数组最右端。返回每个窗口中的最大元素,结果顺序必须与窗口出现顺序一致。
数组长度位于 ``[1, 10^5]``,元素位于 ``[-10^4, 10^4]``,并满足 ``1 <= k <= nums.length``。结果数组长度固定为 ``nums.length-k+1``。不同位置可以拥有相同最大值,每个窗口都必须单独产生一个结果;函数无需修改输入数组。
自建示例
--------
最大值离开窗口后发生变化:
.. code-block:: text
输入:nums = [2, 9, 3, 1, 7, 6],k = 3
输出:[9, 9, 7, 7]
解释:四个窗口依次为 [2,9,3]、[9,3,1]、[3,1,7]、[1,7,6],最大值分别为 9、9、7、7。
窗口长度为 1:
.. code-block:: text
输入:nums = [-2, 4, 0],k = 1
输出:[-2, 4, 0]
解释:每个窗口只包含一个元素,所以结果与原数组相同。
保存仍有资格成为最大值的下标
----------------------------
维护一个双端队列 ``deque``,其中保存窗口内的下标,并满足:
* 下标从队首到队尾递增,队首之外的下标过期时可直接删除;
* 对应值从队首到队尾单调不增,队首就是当前窗口最大值。
处理新下标 ``i`` 时先删除队首所有满足 ``index <= i-k`` 的过期下标;
再从队尾删除所有 ``nums[index] <= nums[i]`` 的下标,因为新元素更晚离开窗口且值不小于它们,
这些旧元素以后不可能成为最大值。最后把 ``i`` 放入队尾;当窗口首次达到长度 ``k`` 时,队首值就是答案。
相等值也可以从队尾删除:保留更晚的那个不会改变最大值,但能让过期管理更简单。
正确性说明
----------
队列中的每个下标都在当前窗口内,且被删除的旧下标要么已经过期,要么被一个更晚且不小于它的新值支配,
所以删除不会丢掉未来可能的最大值。删除完成后,队列值单调不增,队首必为窗口最大值;
窗口每右移一格重复同样维护,故输出的每个值都对应正确窗口。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
std::vector maxSlidingWindow(std::vector& nums, int k) {
std::deque candidates;
std::vector answer;
for (int i = 0; i < static_cast(nums.size()); ++i) {
while (!candidates.empty() && candidates.front() <= i - k) {
candidates.pop_front();
}
while (!candidates.empty() &&
nums[candidates.back()] <= nums[i]) {
candidates.pop_back();
}
candidates.push_back(i);
if (i >= k - 1) {
answer.push_back(nums[candidates.front()]);
}
}
return answer;
}
};
代码分析
--------
每个下标最多入队一次、从队首或队尾出队一次,因此总时间复杂度为 ``O(n)``;双端队列最多保存 ``k`` 个下标,
额外空间为 ``O(k)``,返回数组另占题目要求的输出空间。只保存下标而不是值,才能判断最大值何时离开窗口。