题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个数组和一个数字 k，请给出这个数组中，所有连续 k 个数字中最大的那个数。

思路分享

  • 题目其实已经说明了本题的核心就是滑动窗口了，滑动窗口核心的三步就是进入窗口，弹出窗口，记录数据。

  • 但是从窗口中获得最大值的方式可以改进。最暴力的手段是直接遍历其中的 k 个值外（时间复杂度 (n-k+1)*k），那有没有什么办法能简化呢？

  • 一个简单的办法是设置一个变量维护当前窗口的最大值，当该值弹出时再遍历。能够一定程度上减去部分直接遍历的情况，但对于降序的数组等同于最坏情况。

  • 比较高明的手段是通过单调队列，维护队列内队首到队尾降序，答案就取队首。

    https://leetcode.cn/problems/sliding-window-maximum/solutions/2499715/shi-pin-yi-ge-shi-pin-miao-dong-dan-diao-ezj6/

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque()
        ans = []
        for i, x in enumerate(nums):
            while q and x >= nums[q[-1]]:
                q.pop()
            q.append(i)

            if i - q[0] >= k:
                q.popleft()

            if i >= k-1:
                ans.append(nums[q[0]])

        return ans