题目难度: 简单

原题链接[1]

今天继续更新剑指 offer 系列, 老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了

题目描述

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ 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

题目思考如果要求时间复杂度为 O(N), 该如何做?解决方案思路一个比较容易想到的思路是暴力法, 即固定每个起点, 然后求它之后 k 个元素的最大值并依次加入结果中, 这样时间复杂度为 O(Nk), 当 k 很大的时候效率非常低, 该如何提高效率呢?重新观察题目示例, 如果我们能够动态维护当前窗口的最大值, 那么在窗口移动的时候只需要用 O(1)时间返回这个值即可窗口右移的时候, 如果新加入的值比原来的最大值还要大的话就好办, 直接更新最大值即可但问题来了, 窗口右移意味着左边界也要向右移动, 如果正好之前的左边界是最大值该如何处理呢? 显然只保存最大值一个变量是不够的, 我们也需要保存第二大值, 第三大值...根据上面的分析, 我们需要把这些值保存在一个单调的数据结构中, 一边是窗口里的最大值, 另一边则是最小值窗口右移的时候, 按照顺序分为三部分操作:(当加入当前值后窗口长度会超过 k 时, 即right>=k) 移除老的左边界值: 如果它恰好是最大值, 也移除单调数据结构中对应的值加入新的右边界值: 此时需要先不断移除最小值, 直到当前新值成为新的最小值再插入, 因为更小的值绝不可能成为最大值的候选项(又旧, 值又小)(当加入当前值后窗口长度达到 k 时, 即right>=k-1) 将单调数据结构中保存的最大值加入最终结果中注意上述三个步骤中 3 必须是最后一步, 因为要先调整完当前窗口的最大最小值才行, 而 1 和 2 可以互换位置, 因为可以先处理左边界, 也可以先处理右边界根据上述过程, 我们只需要处理头和尾的插入删除操作, 很显然双端队列就是最合适的数据结构, 两种操作都只需要 O(1)时间下面代码对必要的步骤有详细的解释, 特别是对步骤 1 和 2 的一些关键点的解释, 方便大家理解复杂度时间复杂度 O(N): 每个值最多加入和移出双端队列各一次, 总共 2N 次操作, 所以时间复杂度是 O(N)空间复杂度 O(k): 双端队列最多存 k 个值代码

class Solution:    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:        # 单调双端队列, 左边存窗口最小值, 右边存窗口最大值        q = collections.deque()        res = []        left = 0        for right in range(len(nums)):            # 步骤1 (当加入当前值后窗口长度会超过 k 时, 即right>=k) - 移除老的左边界值: 如果它恰好是最大值, 也移除队列尾            # 注意左边界如果不是最大值的话, 不会存在于队列中, 因为它后面总有更大的值将左边界从队列中淘汰出去 (步骤2的操作)            if right >= k:                if nums[left] == q[-1]:                    q.pop()                left += 1            # 步骤2 (可以和步骤1互换位置) - 加入新的右边界值: 此时需要先不断移除队列左侧最小值, 直到当前新值成为新的最小值再插入左侧, 因为更小的值绝不可能成为最大值的候选项(又旧, 值又小)            # 注意这里需要是小于而不能是小于等于, 因为如果当最小值等于当前值且都被移除的话, 如果它恰好也是最大值, 那么下次移除左边界的时候就会错误地将当前的值给移除, 而不是移除左边界对应的那个值, 这样会导致后面的最大值计算出现错误            while q and q[0] < nums[right]:                q.popleft()            q.appendleft(nums[right])            # 步骤3 (当加入当前值后窗口长度达到 k 时, 即right>=k-1) - 将队列右侧最大值加入最终结果中            if right >= k - 1:                res.append(q[-1])        return res

参考资料

[1]

原题链接: