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)``,返回数组另占题目要求的输出空间。只保存下标而不是值,才能判断最大值何时离开窗口。