单调栈与单调队列终极对决：滑动窗口最大值（LeetCode 239）与接雨水（LeetCode 42）底层双模型穿透
在算法题库与大厂面试高频 Hard 题中，“单调栈（Monotonic Stack）”与“单调队列（Monotonic Queue）”是一对名字极度相似、但在解决的问题维度、内部元素的进出机制、以及空间淘汰法则上截然不同的高级线性数据结构。
经典标志性题型：
- LeetCode 239：滑动窗口最大值（Sliding Window Maximum）（单调队列标志性题）；
- LeetCode 42：接雨水（Trapping Rain Water）（单调栈 vs 双指针双解法）；
- LeetCode 862：和至少为 K 的最短子数组（前缀和 + 单调双端队列）；
- LeetCode 84：柱状图中最大的矩形（单调栈标志性题）。
很多同学在面对具体题目时，经常分不清：
到底什么时候用单调栈？什么时候用单调队列？
为什么单调队列必须使用双端队列（Deque）？双端队列的两端淘汰分别对应着什么物理含义？
单调栈的**“行切法（按层横向累加）”与双指针的“列切法（按列纵向累加）”**在接雨水中是如何形成数学对偶的？
今天我们把单调栈与单调队列的核心区别、底层淘汰状态机、以及两大经典 Hard 题的工业级代码彻底讲透。
单调栈 vs 单调队列核心特性全景对比
graph TD subgraph 单调栈 (Monotonic Stack: 解决【局部最近】极值) S1[操作端点: 仅在栈顶一端执行 Push / Pop] S2[核心应用: 寻找左侧/右侧【第一个更大/更小】的元素 (Next Greater Element)] S3[淘汰机制: 被入栈的新元素在数值上强行弹出 (压扁)] end subgraph 单调队列 (Monotonic Queue: 解决【滑动区间】极值) Q1[操作端点: 队尾插入/淘汰数值较小者, 队头淘汰超出窗口范围者 (双端 Deque)] Q2[核心应用: 动态滑动窗口 [i-k+1, i] 内的【全局最大/最小值】] Q3[淘汰机制: 1. 队尾按数值淘汰 (维护单调性); 2. 队头按生命周期/过期时间淘汰!] end| 对比维度 | 单调栈（Monotonic Stack） | 单调队列（Monotonic Queue） |
|---|---|---|
| 底层核心容器 | 单端栈（ArrayDeque/int[] stack） | 双端队列（Deque，两头都可弹出） |
| 元素淘汰动因 | 纯粹由**“新元素的数值大小”**触发弹出 | 双重淘汰：队尾由数值大小淘汰，队头由“窗口滑动过期”淘汰 |
| 解决的问题模型 | 寻找某个元素单侧第一个比它大/小的边界 | 维护一个动态移动区间内的最值（RMQ） |
| 时间复杂度 | $\mathcal{O}(N)$（每个元素最多进出栈 1 次） | $\mathcal{O}(N)$（每个元素最多进出队 1 次） |
一、单调队列实战：滑动窗口最大值（LeetCode 239）
问题：给定数组nums和窗口大小k，窗口每次向右滑动 1 步，求每个窗口内的最大值。
单调队列核心哲学：
“如果一个新加入的选手比你年轻（位置靠后），且比你更强（数值更大），那么你将永远没有出头之日，可以直接光荣退役了！”
graph LR subgraph 单调递减双端队列 (队头恒为当前窗口最大值) Head[队头: 存储当前最大值索引] <---> Mid[中间元素] <---> Tail[队尾: 新元素入队] end NewElem[新元素 nums i 准备入队] -->|1. 队尾淘汰: 若队尾元素 <= nums i, 循环从队尾弹出!| Tail WindowSlide[窗口向右滑动] -->|2. 队头过期: 若队头索引 <= i - k, 从队头弹出!| Head工业级 Java 实现代码：
import java.util.ArrayDeque; import java.util.Deque; public class SlidingWindowMaxSolution { public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; if (n == 0 || k == 0) return new int[0]; int[] result = new int[n - k + 1]; // 双端队列：存储数组下标索引 (保证下标对应的值单调严格递减) Deque<Integer> deque = new ArrayDeque<>(); for (int i = 0; i < n; i++) { // 1. 队头过期检查：移除滑出当前窗口 [i-k+1, i] 的旧下标 if (!deque.isEmpty() && deque.peekFirst() <= i - k) { deque.pollFirst(); } // 2. 队尾维护单调性：将所有比当前 nums[i] 小的元素全部从队尾弹出 (它们永无出头之日) while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) { deque.pollLast(); } // 3. 将当前索引加入队尾 deque.offerLast(i); // 4. 记录结果：当窗口形成后，队头下标对应的值必然是当前窗口的最大值！ if (i >= k - 1) { result[i - k + 1] = nums[deque.peekFirst()]; } } return result; } }二、单调栈实战：接雨水（LeetCode 42）的“横向切片法”
接雨水可以通过双指针纵向按列求，但单调递减栈能够极其优雅地通过**“横向按凹槽切片”**计算雨水量：
graph TD A[单调递减栈: 遇到比栈顶高的柱子, 出现凹槽!] --> Pop[弹出栈顶作为凹槽底部 mid] Pop --> Check{弹出后栈为空?} Check -->|是: 左侧无墙, 无法蓄水| Skip[跳过] Check -->|否: 栈顶为左墙 left, 当前柱子为右墙 right| Calc[计算水洼高度: min(height left, height right) - height mid] Calc --> Area[水洼面积 = 高度 * 水平跨度 (right - left - 1)]工业级单调栈解法代码：
import java.util.ArrayDeque; import java.util.Deque; public class TrappingRainWaterSolution { public int trap(int[] height) { int n = height.length; int totalWater = 0; // 单调递减栈：存储柱子的下标 Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < n; i++) { // 当当前柱子高于栈顶柱子时，说明形成了一个凹坑洼地！ while (!stack.isEmpty() && height[i] > height[stack.peek()]) { int mid = stack.pop(); // 凹坑底部的索引 if (stack.isEmpty()) { break; // 左侧没有更高的墙，水直接流走，无法蓄水 } int left = stack.peek(); // 左侧边界墙的索引 int right = i; // 右侧边界墙的索引 // 凹槽能够蓄水的有效高度 int boundedHeight = Math.min(height[left], height[right]) - height[mid]; // 凹槽的水平宽度 int distance = right - left - 1; totalWater += boundedHeight * distance; // 累加横向切片雨水量 } stack.push(i); } return totalWater; } }选型判断决策口诀
“区间动态最值选单调队列，队头控滑动窗口，队尾维护单调；”
“左右边界极值选单调栈，入栈破单调，出栈算面积！”
实习生的算法总结
单调栈与单调队列是线性时间复杂度算法中的“降维武器”。
它们利用严格单调性的数学约束，将原本需要两层嵌套遍历的 $\mathcal{O}(N^2)$ 暴力扫描，优雅压缩为每个元素进出容器至多 1 次的严格 $\mathcal{O}(N)$。
搞懂了双端队列两头淘汰的物理因果与单调栈凹槽的形成机制，面对任何关于区间滑动最值与几何包络计算的难题，你都能秒级写出最优解。
