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]总结本题是单调队列的经典应用问题主要考察对单调队列数据结构的理解和使用。通过使用单调队列我们可以高效地找到滑动窗口中的最大值。单调队列的核心思想是使用队列来存储窗口中的元素索引队列中的元素对应的数值是递减的当遇到更大的元素时弹出队列尾部的较小元素当队列头部元素超出窗口范围时弹出队列头部元素。这种方法不仅适用于滑动窗口最大值问题还可以应用于许多其他需要滑动窗口操作的问题。掌握单调队列的使用对于解决这类问题非常重要。