核心内容摘要
存在即对话：方见华对话本体论与世毫九理论的数学奠基、形式证明与工程实现
LeetCode
滑动窗口最大值 - 单调队列解法详解
问题理解问题描述给定一个整数数组 nums 和一个整数 k滑动窗口从数组的最左侧移动到最右侧每次只向右移动一位。
请找出所有滑动窗口中的最大值并返回这些最大值组成的数组。
示例text输入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 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7
核心思路单调队列维护潜在最大值暴力解法的局限性对于每个窗口都重新遍历 k 个元素找最大值时间复杂度为 O(nk)效率极低。
单调队列优化思路单调队列定义使用双端队列Deque维护一个单调递减的队列存储元素的索引。
队列特性队列中的索引对应的元素值从队首到队尾单调递减。
队首元素总是当前窗口的最大值。
维护操作入队新元素入队时从队尾开始移除所有小于等于它的元素然后入队。
出队检查队首元素是否还在当前窗口内如果不在则移除。
获取最大值窗口完全形成后队首元素即为当前窗口最大值。
代码逐行解析Java 解法javaimport java.util.ArrayDeque;import java.util.Deque;class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n nums.length;//
结果数组滑动窗口的个数为 n - k 1int[] ans new int[n - k 1];//
双端队列存储元素索引维护队列内元素值单调递减DequeInteger q new ArrayDeque();//
遍历数组的每个元素for (int i 0; i n; i) {//
1 新元素从队尾入队维护队列单调性// 从队尾开始移除所有小于等于当前元素的索引// 因为这些元素不可能成为后续窗口的最大值while (!q.isEmpty() nums[q.getLast()] nums[i]) {q.removeLast();}// 将当前元素索引加入队尾q.addLast(i);//
2 移除窗口外的元素// 计算当前窗口的左边界int left i - k 1;// 如果队首索引小于左边界说明队首元素不在当前窗口内if (q.getFirst() left) {q.removeFirst();}//
3 当窗口完全形成时记录当前窗口最大值// 当 left 0 时窗口已包含 k 个元素if (left
{ans[left] nums[q.getFirst()];}}//
返回结果return ans;}}Python 解法pythonfrom collections import dequefrom typing import Listclass Solution:def maxSlidingWindow(self, nums: List[int], k: int) - List[int]:n len(nums)#
边界处理if n 0 or k 0:return []#
初始化结果数组和双端队列ans [0] * (n - k
q deque()#
遍历数组for i in range(n):#
1 维护队列单调性# 从队尾开始移除所有小于等于当前元素的索引while q and nums[q[-1]] nums[i]:q.pop()# 将当前索引加入队尾q.append(i)#
2 移除窗口外的元素# 计算当前窗口的左边界left i - k 1# 如果队首索引小于左边界说明不在当前窗口内if q[0] left:q.popleft()#
3 记录结果当窗口完全形成时if left 0:ans[left] nums[q[0]]#
返回结果return ans
Java 与 Python 语法对比
队列操作操作 Java Python创建双端队列 DequeInteger q new ArrayDeque(); q deque()获取队尾元素 q.getLast() q[-1]移除队尾元素 q.removeLast() q.pop()获取队首元素 q.getFirst() q[0]移除队首元素 q.removeFirst() q.popleft()添加元素到队尾 q.addLast(i) q.append(i)
数组/列表操作操作 Java Python创建数组 int[] ans new int[n - k 1]; ans [0] * (n - k
获取数组长度 nums.length len(nums)获取数组元素 nums[i] nums[i]
循环与控制流操作 Java Pythonfor 循环 for (int i 0; i n; i) for i in range(n):while 循环 while (!q.isEmpty() ...) while q and ...:
实例演示以测试用例 nums [1, 3, -1, -3, 5, 3, 6, 7], k 3 为例演示过程步骤 i nums[i] 队列操作维护单调性后 队列索引值 left 队首在窗口内 ans[left]1 0 1 空队列直接加入0 [0(
] -2 不判断 -2 1 3 1(
0(
移除0加入1 [1(
] -1 不判断 -3 2 -1 队尾1(
-1直接加入2 [1(
, 2(-
] 0 是 (
ans[0]34 3 -3 队尾2(-
-3直接加入3 [1(
, 2(-
, 3(-
] 1 是 (
ans[1]35 4 5 依次移除3(-
, 2(-
, 1(
加入4 [4(
] 2 是 (
ans[2]56 5 3 队尾4(
3直接加入5 [4(
, 5(
] 3 是 (
ans[3]57 6 6 移除5(
, 4(
加入6 [6(
] 4 是 (
ans[4]68 7 7 移除6(
加入7 [7(
] 5 是 (
ans[5]7最终结果ans [3, 3, 5, 5, 6, 7]
关键细节解析
为什么队列存储索引而不是值索引可以判断元素是否在窗口内通过比较索引和窗口左边界可以知道元素是否已经滑出窗口。
值无法判断位置如果只存储值无法知道该值对应的元素是否还在当前窗口内。
为什么入队时要移除小于等于当前元素的队尾元素假设队列尾部有元素 x当前元素为 y且 x yy 比 x 更大或相等且更靠右索引更大。
在后续窗口中y 会比 x 更晚离开窗口。
因此x 永远不可能成为后续窗口的最大值可以安全移除。
窗口何时完全形成当 i k - 1 时left i - k 1 0此时窗口包含 k 个元素可以记录最大值。
为什么队首一定是当前窗口的最大值队列维护了从队首到队尾的单调递减性。
队首元素是当前窗口中最早加入队列且未被移除的元素。
通过入队时的筛选队首元素一定大于队列中其他元素且在当前窗口内。
复杂度分析时间复杂度O(n)每个元素最多入队一次、出队一次。
每个元素的操作次数是常数级别。
总操作次数为 O(n)。
空间复杂度O(k)队列中最多同时存储 k 个元素当数组单调递减时。
结果数组 O(n-k
不计入空间复杂度属于输出要求。
优化技巧与变体
处理边界情况pythondef maxSlidingWindow(self, nums: List[int], k: int) - List[int]:if not nums or k 0:return []n len(nums)if k 1:return numsif k n:return [max(nums)]# 后续逻辑...
使用数组模拟双端队列优化空间pythondef maxSlidingWindow(self, nums: List[int], k: int) - List[int]:n len(nums)if n 0 or k 0:return []# 使用列表模拟双端队列q [0] * n # 预分配空间front, rear 0, -1 # 队列的头部和尾部指针ans [0] * (n - k
for i in range(n):# 维护队列单调性while front rear and nums[q[rear]] nums[i]:rear - 1rear 1q[rear] i# 移除窗口外的元素if q[front] i - k 1:front 1# 记录结果if i k - 1:ans[i - k 1] nums[q[front]]return ans
使用优先队列堆的解法pythonimport heapqfrom typing import Listclass Solution:def maxSlidingWindow(self, nums: List[int], k: int) - List[int]:if not nums or k 0:return []n len(nums)# 使用最大堆存储-值索引对因为Python的heapq是最小堆heap []result []for i in range(n):# 将当前元素加入堆中heapq.heappush(heap, (-nums[i], i))# 当窗口完全形成时if i k - 1:# 移除堆顶不在窗口内的元素while heap and heap[0][1] i - k:heapq.heappop(heap)# 堆顶元素就是当前窗口的最大值result.append(-heap[0][0])return result复杂度分析时间复杂度O(n log n)每个元素入堆出堆需要 O(log n)空间复杂度O(n)缺点比单调队列解法慢但逻辑更简单。
常用函数积累Java 常用函数java// 双端队列操作DequeInteger deque new ArrayDeque();deque.addLast(element); // 添加到队尾deque.removeLast(); // 移除队尾deque.getLast(); // 获取队尾deque.addFirst(element); // 添加到队首deque.removeFirst(); // 移除队首deque.getFirst(); // 获取队首deque.isEmpty(); // 判断队列是否为空deque.size(); // 获取队列大小// 数组操作int[] arr new int[n];int length arr.length; // 数组长度Arrays.fill(arr, value); // 填充数组Python 常用函数pythonfrom collections import deque# 双端队列操作q deque()q.append(element) # 添加到队尾q.pop() # 移除队尾q[-1] # 获取队尾q.appendleft(element) # 添加到队首q.popleft() # 移除队首q[0] # 获取队首len(q) # 获取队列大小bool(q) # 判断队列是否非空# 列表操作arr [0] * nlen(arr) # 列表长度max(arr) # 获取最大值min(arr) # 获取最小值
十、
总结核心要点单调队列是关键维护一个单调递减的队列队首元素始终是当前窗口的最大值。
索引存储很重要存储索引而非值可以方便地判断元素是否在窗口内。
时间复杂度优化从暴力解法的 O(nk) 优化到 O(n)。
面试
常见问题为什么使用单调队列而不是优先队列单调队列的均摊时间复杂度是 O(
而优先队列是 O(log n)。
单调队列更适合滑动窗口问题因为元素是按顺序加入和移除的。
如何处理数组中有重复元素的情况算法天然支持重复元素因为入队时移除的是小于等于当前元素的元素。
如果有多个相同的最大值队列中会保留最右侧的那个索引最大的。
如果 k 很大接近 n 怎么办算法仍然有效队列大小最多为 k空间复杂度 O(k)。
当 k n 时只需要返回整个数组的最大值。
最坏情况下的时间复杂度每个元素最多入队一次、出队一次所以是 O(n)。
如果数组是单调递增的队列会怎样队列中最多只会有一个元素因为每个新元素都会移除之前的所有元素。
扩展思考类似问题滑动窗口最小值只需将单调递减改为单调递增滑动窗口的中位数需要更复杂的数据结构滑动窗口的平均值更简单只需维护窗口和变体问题限制大小的队列最大值队列有最大容量需要支持push和pop二维滑动窗口最大值更复杂需要结合单调队列和动态规划实际应用股票价格分析寻找一段时间内的最高价网络流量监控统计固定时间窗口内的最大流量图像处理滑动窗口滤波器掌握单调队列的解法不仅能够解决滑动窗口最大值问题还能够解决一系列类似的区间最值问题是面试中非常重要的算法技巧。
————————————————版权声明本文为CSDN博主「好学且牛逼的马」的原创文章遵循CC
0 BY-SA版权协议转载请附上原文出处链接及本声明。
原文链接https://blog.csdn.net/King_model/article/details/154684394