LeetCode 滑动窗口最大值题解

LeetCode 滑动窗口最大值题解题目描述给定一个数组和一个窗口大小 k返回每个窗口中的最大值。示例输入nums [1,3,-1,-3,5,3,6,7],k 3输出[3,3,5,5,6,7]解题思路方法单调队列思路使用单调递减队列存储元素的索引。遍历数组对于每个元素从队列末尾移除所有小于当前元素的元素将当前元素的索引加入队列如果队列头部的索引已经不在当前窗口内则移除当遍历到第 k 个元素及之后将队列头部的元素加入结果列表复杂度分析时间复杂度O(n)空间复杂度O(k)代码实现from collections import deque 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() 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()总结滑动窗口最大值是单调队列的典型应用通过维护一个单调递减队列来找出每个窗口中的最大值。