LeetCode 239. Sliding Window Maximum 题解
LeetCode 239. Sliding Window Maximum 题解
题目描述
给你一个整数数组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]示例 3：
输入：nums = [1,-1], k = 1 输出：[1,-1]示例 4：
输入：nums = [9,11], k = 2 输出：[11]示例 5：
输入：nums = [4,-2], k = 2 输出：[4]解题思路
方法：单调队列
思路：
- 使用单调队列来存储窗口中的元素索引，队列中的元素对应的数值是递减的
- 遍历数组，对于每个元素：
- 当队列不为空且当前元素大于队列尾部元素对应的数值时，弹出队列尾部元素
- 将当前元素的索引压入队列
- 当队列头部元素的索引超出窗口范围时，弹出队列头部元素
- 当遍历的元素索引大于等于 k-1 时，将队列头部元素对应的数值加入结果列表
复杂度分析：
- 时间复杂度：O(n)，其中 n 是数组的长度。每个元素最多被压入和弹出队列一次。
- 空间复杂度：O(k)，最坏情况下，队列需要存储 k 个元素。
代码实现
方法：单调队列
class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: # 初始化结果列表和单调队列 result = [] deque = [] n = len(nums) # 遍历数组 for i in range(n): # 当队列不为空且当前元素大于队列尾部元素对应的数值时，弹出队列尾部元素 while deque and nums[i] > nums[deque[-1]]: deque.pop() # 将当前元素的索引压入队列 deque.append(i) # 当队列头部元素的索引超出窗口范围时，弹出队列头部元素 while deque[0] <= i - k: deque.pop(0) # 当遍历的元素索引大于等于 k-1 时，将队列头部元素对应的数值加入结果列表 if i >= k - 1: result.append(nums[deque[0]]) return result测试用例
测试用例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
测试用例 2：
输入：nums = [1], k = 1
输出：[1]
测试用例 3：
输入：nums = [1,-1], k = 1
输出：[1,-1]
测试用例 4：
输入：nums = [9,11], k = 2
输出：[11]
测试用例 5：
输入：nums = [4,-2], k = 2
输出：[4]
总结
本题是单调队列的经典应用问题，主要考察对单调队列数据结构的理解和使用。通过使用单调队列，我们可以高效地找到滑动窗口中的最大值。
单调队列的核心思想是：使用队列来存储窗口中的元素索引，队列中的元素对应的数值是递减的，当遇到更大的元素时，弹出队列尾部的较小元素，当队列头部元素超出窗口范围时，弹出队列头部元素。
这种方法不仅适用于滑动窗口最大值问题，还可以应用于许多其他需要滑动窗口操作的问题。掌握单调队列的使用，对于解决这类问题非常重要。