单调队列——“窗口内最值“的 O(n) 答案

滑动窗口最大值这道 Hard暴力 O(nk)单调队列 O(n)。从淘汰不可能当最大值的废物讲起三语言实现 239再进阶 1438 双单调队列。示例手算验证全程推演。引子一道 Hard卡住无数人的不是代码是思维nums [1,3,-1,-3,5,3,6,7]窗口大小k 3每次右移一格返回窗口最大值[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 ...这是LeetCode 239 滑动窗口最大值Hard[1]。暴力每个窗口重扫一遍k 接近 n 时退化成 O(n²)。答案是一个经典数据结构单调队列。一、问题滑动窗口最大值为什么是 Hard1.1 暴力解与它的两个浪费暴力复杂度 O(n·k)[1]。两个浪费重复比较相邻窗口共享元素被反复比较信息不传递上一次谁最大没有带到下一次核心洞察窗口只滑出 1 个、滑入 1 个元素暴力却重扫 k 个——这就是 O(nk) 的来源。二、单调队列原理只留候选淘汰废物2.1 双端队列 单调递减单调队列是双端队列存下标满足不变量[1][3]队内下标递增对应值严格单调递减队首即窗口最大值。2.2 两条维护规则规则一入队淘汰新元素入队前从队尾弹出所有≤ nums[i]的元素。为什么安全被弹出的老元素① 值 ≤ 新元素② 下标更早存活更短。在新元素存活期间老元素永远不可能成为最大值——比它小还比它先出窗口。既然永远赢不了就永久淘汰[1]。规则二出窗清理若队首下标 i-k1从队首弹出。2.3 均摊 O(1)每个元素最多入队一次、出队一次总数被 n 封顶——均摊 O(1)总复杂度 O(n)[1][4]。三、239 三语言实现工程关键存下标不存值——只有下标能判断是否滑出窗口[1]。3.1 Cclass Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { dequeint q; // 存下标值单调递减 vectorint ans; for (int i 0; i nums.size(); i) { while (!q.empty() nums[q.back()] nums[i]) q.pop_back(); // 入队淘汰 q.push_back(i); if (q.front() i - k) q.pop_front(); // 出窗清理 if (i k - 1) ans.push_back(nums[q.front()]); } return ans; } };3.2 Pythonfrom collections import deque class Solution: def maxSlidingWindow(self, nums: list[int], k: int) - list[int]: q deque() ans [] for i, x in enumerate(nums): while q and nums[q[-1]] x: q.pop() q.append(i) if q[0] i - k: q.popleft() if i k - 1: ans.append(nums[q[0]]) return ans3.3 Javaclass Solution { public int[] maxSlidingWindow(int[] nums, int k) { DequeInteger q new ArrayDeque(); int n nums.length; int[] ans new int[n - k 1]; for (int i 0; i n; i) { while (!q.isEmpty() nums[q.peekLast()] nums[i]) q.pollLast(); q.offerLast(i); if (q.peekFirst() i - k) q.pollFirst(); if (i k - 1) ans[i - k 1] nums[q.peekFirst()]; } return ans; } }3.4 手算推演nums [1,3,-1,-3,5,3,6,7], k3 i0: 入队[0] → 窗口未满 i1: 31弹出0入队[1] → 窗口未满 i2: -1入队[1,2]队首3 → 答案[3] i3: -3入队[1,2,3]队首3 → 答案[3,3] i4: 5 -3,-1,3全弹入队[4] → 答案[3,3,5] i5: 3入队[4,5]队首5 → 答案[3,3,5,5] i6: 63,5全弹入队[6]队首6 → 答案[3,3,5,5,6] i7: 76全弹入队[7]队首7 → 答案[3,3,5,5,6,7]-3、-1这类小元素被后来的5一次清空——它们永远当不了最大值。四、进阶1438 双单调队列4.1 问题转化LeetCode 1438找最长连续子数组满足max - min ≤ limit[2]。关键升级同时维护 max 和 min——一个递减队列存 max一个递增队列存 min[2]。4.2 Python 实现from collections import deque class Solution: def longestSubarray(self, nums: list[int], limit: int) - int: maxQ, minQ deque(), deque() l ans 0 for r, x in enumerate(nums): while maxQ and nums[maxQ[-1]] x: maxQ.pop() while minQ and nums[minQ[-1]] x: minQ.pop() maxQ.append(r) minQ.append(r) while nums[maxQ[0]] - nums[minQ[0]] limit: if maxQ[0] l: maxQ.popleft() if minQ[0] l: minQ.popleft() l 1 ans max(ans, r - l 1) return ans4.3 为什么仍然 O(n)双指针各移动 n 次单调队列均摊 O(1)——总复杂度 O(n)[2]。举一反三价值单调队列不只会找一个最值还能同时维护多个最值支撑窗口合法性判断。五、单调栈 vs 单调队列 我的心得5.1 对比表维度单调栈739/84单调队列239/1438底层栈单端双端队列单调方向递增/递减均可递减存 max / 递增存 min回答的问题两侧第一个更大/更小窗口内最值淘汰依据被夹在中间失去候选资格更小且更早永远赢不了典型题739 每日温度、84 柱状图239、1438、14255.2 三条心得心得一单调结构 淘汰不可能。栈和队列的本质都是新元素出现时把永远不可能成为答案的旧元素淘汰。理解为什么淘汰是安全的比背模板重要。心得二存下标是工程灵魂。否则无法判断元素是否滑出窗口。心得三从单最值到双最值是能力复用。1438 只是把 239 的队列复制一份反方向——单调队列是可组合的原语。单调队列是滑动窗口问题的终极形态O(n) 时间、O(k) 空间把暴力里被浪费的比较全部回收。参考资料[1] LeetCode 239 官方题解一级[2] LeetCode 1438 官方题解一级[3] 算法教材双端队列与滑动窗口结构二级[4] 力扣讨论区单调队列复杂度证明三级