LeetCode 滑动窗口最大值II题解题目描述给定一个数组nums和一个窗口大小k滑动窗口每次向右移动一位。返回每个窗口中的最大值。示例输入nums [1,3,-1,-3,5,3,6,7],k 3输出[3,3,5,5,6,7]解题思路方法单调队列思路使用单调队列来解决这个问题。单调队列是一个双端队列维护一个递减的序列。遍历数组对于每个元素从队列末尾移除所有小于当前元素的元素。将当前元素的索引加入队列。如果队列头部的索引已经不在当前窗口内将其移除。当遍历到第 k 个元素及之后将队列头部的元素加入结果列表。复杂度分析时间复杂度O(n)其中 n 是数组的长度。每个元素最多被加入和移除队列一次。空间复杂度O(k)队列中最多存储 k 个元素。代码实现方法单调队列from collections import deque # 滑动窗口最大值 II单调队列 def max_sliding_window(nums, k): if not nums or k 0: return [] queue deque() result [] for i in range(len(nums)): # 从队列末尾移除所有小于当前元素的元素 while queue and nums[i] nums[queue[-1]]: queue.pop() # 将当前元素的索引加入队列 queue.append(i) # 如果队列头部的索引已经不在当前窗口内将其移除 while queue[0] i - k: queue.popleft() # 当遍历到第 k 个元素及之后将队列头部的元素加入结果列表 if i k - 1: result.append(nums[queue[0]]) return result # 测试 def test_max_sliding_window(): nums [1, 3, -1, -3, 5, 3, 6, 7] k 3 print(max_sliding_window(nums, k)) # 输出[3, 3, 5, 5, 6, 7] if __name__ __main__: test_max_sliding_window()测试用例测试用例 1基本情况输入nums [1,3,-1,-3,5,3,6,7],k 3输出[3,3,5,5,6,7]测试用例 2窗口大小为1输入nums [1,2,3,4,5],k 1输出[1,2,3,4,5]总结滑动窗口最大值 II 是一个经典的单调队列问题它可以通过单调队列来高效地解决。单调队列的核心思想是维护一个递减的序列队列头部始终是当前窗口的最大值。掌握单调队列的使用方法对于解决类似的问题非常重要。