Leetcode 239. 滑动窗口最大值 239. 滑动窗口最大值题目描述给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值。示例 1输入：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示例 2输入：nums = [1], k = 1 输出：[1]提示1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length题解笔记：暴力、大顶堆、单调队列一、先理解题目本质这道题的核心是：窗口大小固定为 k窗口不断向右滑动每次都要快速得到当前窗口的最大值最直接的想法是： 每形成一个窗口，就把窗口里的元素都扫一遍，找最大值。这就是暴力解法。但如果数组很长，每次都重新扫，会有很多重复计算，所以就会继续优化到：大顶堆单调队列解法一：暴力解法思路每次窗口形成后，直接遍历这个窗口里的所有元素，找到最大值。例如窗口是：[3, -1, -3]那就把这 3 个数重新比较一遍，得到最大值 3。代码from typing import List class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: ans = [] for left in range(len(nums) - k + 1): max_num = nums[left] for right in range(left, left + k): max_num = max(max_num, nums[right]) ans.append(max_num) return ans复杂度时间复杂度：O(n * k)空间复杂度：O(1)（不算返回结果）优缺点优点最容易理解非常适合刚开始学这题时打基础缺点每个窗口都重新扫描一遍重复计算很多数据大时容易超时解法二：大顶堆先说结论大顶堆可以做，而且比暴力解法更高效。 不过它不是最优解，通常复杂度是：时间复杂度：O(n log n)（严格说更稳妥）空间复杂度：O(n)1. 为什么会想到堆因为这题每次都在问：当前窗口里的最大值是谁？而堆最擅长做的事就是：插入一个数快速拿到最大值（或最小值）所以一个很自然的想法就是：把窗口相关元素放进堆里每次从堆顶拿最大值2. 但为什么不能直接只存值问题在于： 窗口会向右移动，旧元素会离开窗口。例如：[3, -1, -3]下一步变成：[-1, -3, 5]这里的 3 已经离开窗口了。 但如果它还在堆里，并且还在堆顶，那就会影响答案。所以只存值不够，还必须存：值下标3. 为什么 Python 里要存 (-值, 下标)因为 Python 的 heapq 默认是小顶堆，没有原生大顶堆。所以我们常用一个技巧：把值取负原本最大的值，负数后反而最小这样小顶堆就能模拟大顶堆例如数字 5，下标为 4，会存成：(-5, 4)其中：-5：用来模拟大顶堆4：表示它原来的下标4. 什么叫“过期元素”假设当前窗口范围是：[left, right]如果某个元素的下标：idx < left就说明它已经滑出窗口，不能再参与当前窗口最大值比较了。这类元素就叫：过期元素5. 什么叫“懒删除”堆不擅长删除中间任意位置的元素。所以我们不主动去堆里搜索并删除所有过期元素，而是：只要堆顶过期，就把堆顶弹出一直弹到堆顶合法为止这就叫：懒删除代码里通常是：while heap[0][1] < left: heapq.heappop(heap)代码from typing import List import heapq class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: heap = [] ans = [] for i, num in enumerate(nums): # 入堆：(-值, 下标) heapq.heappush(heap, (-num, i)) # 窗口形成后再开始记录答案 if i >= k - 1: left = i - k + 1 # 懒删除：弹掉所有过期堆顶 while heap[0][1] < left: heapq.heappop(heap) # 堆顶就是当前窗口最大值 ans.append(-heap[0][0]) return ans堆解法动画复杂度时间复杂度：O(n log n)空间复杂度：O(n)优缺点优点思路比单调队列更直观很适合从暴力解法继续进阶也能解决这道题缺点不是最优解代码里要理解“过期元素”和“懒删除”堆中可能保留一些已经过期但暂时不在堆顶的元素解法三：单调队列先说结论这是这道题的最优解。时间复杂度：O(n)空间复杂度：O(k)1. 核心思想我们希望队列里维护的是：可能成为当前窗口最大值的元素下标并且让这些下标对应的值，保持单调递减。也就是说：队首最大队尾最小这样每次窗口形成后：队首就是当前窗口最大值的下标直接取 nums[deque[0]] 就行2. 为什么要存下标，不直接存值因为窗口会移动，我们需要判断队首元素是否已经离开窗口。如果只存值，就不知道它对应的是哪个位置。所以单调队列里存的是：下标3. 队列维护规则遍历到 i 时，做三件事。第一步：移除队首过期元素如果队首下标已经不在窗口内：deque[0] < i - k + 1就把它弹掉。第二步：保持单调递减如果当前元素 nums[i] 比队尾对应的值还大，那么队尾那个元素以后就不可能成为最大值了。因为：它比当前元素小它还比当前元素更早过期所以直接弹出队尾，直到队列重新单调递减。第三步：把当前下标加入队尾这样队列中保留的，都是未来仍有机会成为最大值的元素。代码from typing import List from collections import deque class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: q = deque() ans = [] for i, num in enumerate(nums): # 1. 删除窗口左边已经过期的下标 while q and q[0] < i - k + 1: q.popleft() # 2. 维护单调递减队列 while q and nums[q[-1]] < num: q.pop() # 3. 当前下标加入队尾 q.append(i) # 4. 窗口形成后，队首就是最大值 if i >= k - 1: ans.append(nums[q[0]]) return ans复杂度时间复杂度：O(n)空间复杂度：O(k)为什么是 O(n)因为每个元素最多只会：进队一次出队一次不会反复进出，所以总操作次数和 n 成正比。优缺点优点最优解性能最好是这道题的经典标准答案缺点对初学者来说抽象一点第一次接触“单调队列”时不如堆直观