[239][困难][队列] 滑动窗口最大值

题目描述

239. 滑动窗口最大值 剑指 Offer 59 - I. 滑动窗口的最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

进阶：

你能在线性时间复杂度内解决此题吗？

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

提示：

• 1 <= nums.length <= 10^5

• -10^4 <= nums[i] <= 10^4

• 1 <= k <= nums.length

解题思路

与[155][简单][栈] 最小栈中的解题思路类似, 本题也需要构造一个辅助数据结构, 用来存储一些中间值, 辅助求解每个窗口对应的最大值. 题目中, 滑动窗口的移动形式, 其实就是队列这种数据接口元素入队和出队的方式, 那么在选取辅助结构时, 首先考虑的就是使用辅助队列.

与最小栈的辅助栈直白的作用不同, 本题中辅助队列的使用方式不是很直观. 我们要利用对接的特殊性质, 观察原始列表中前后两个元素a和b, a在b之前, 如果a小于b, 那么在b出现之后, a就绝不可能在任何一个窗口中是最大值, 换句话说, 如果遇到了这种关系的a和b, 在b出现的时候, a就没有记录的必要了, 就可以被抛弃掉了.

秉承这种思路, 我们设计辅助队列的存储内容和更新方式. 与辅助栈元素与主栈一一对应的关系不同, 辅助队列的更新逻辑程是这样的:

• 对于新来的数字, 我们从队列的尾部开始, 依次判断尾部的元素是否小于这个新的数字num, 如果小于, 则就遇到了上面所述的场景, 因此将队尾元素弹出抛弃, 继续检查新的队尾元素是否符合条件, 直到队列中没有任何元素, 或队尾的元素不小于num

  • 这样得到的队列是一个递减序列, 而队列的首个元素, 就代表了在当前窗口下的最大值

• 然后考虑被移出窗口的数字last

  • 如果last在被移出之前, 不是窗口中的最大值, 那么它肯定不在队列中, 因为在窗口最大值入栈的过程中(或者更早), last就已经被移出队列了

  • 如果是最大值, 那么它肯定是在队列的首位. 我们可以通过比较移出窗口的数字和队列首位的元素值是否相等, 来判断当前队列的最大值是否应该被移出, 如果满足, 则将队列的首位(最左端)的元素移出

可以看到我们使用的辅助队列是一个双向队列. 元素从右端添加, 从左右两端都可能弹出. 那么会不会出现辅助队列超长(超过窗口长度k)的现象呢, 因为这意味着还有窗口之外的元素被考虑, 从而得到的结果可能错误.

如果队列的长度等于窗口的大小, 说明当前窗口的每一个值都在队列中, 而按照添加的逻辑, 说明当前窗口的元素肯定是满足递减规律的, 否则就会有元素被踢出队列. 而这又说明窗口中的第一个元素就是窗口的最大值. 那么在新的元素进入时, 原窗口中第一个元素被移出窗口, 而它也是对应的最大值, 根据规则也会被移出队列, 新的元素被添加到队列中.

因此按照先判断剔除最大元素, 然后调整队列内容, 添加新元素的顺序操作, 就不可能出现辅助队列超长现象. 从而保证了结果的正确性.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if k == 1:
            return nums

        n = len(nums)
        deq = deque()

        def adjust(num, last):
            if last is not None and last == deq[0]:
                deq.popleft()
            while deq and deq[-1] < num:
                deq.pop()
            deq.append(num)

        res = []
        for i, num in enumerate(nums):
            if i < k - 1:
                adjust(num, None)
            else:
                adjust(num, nums[i - k])
                res.append(deq[0])
        return res