单调栈是一种特殊的栈结构，它始终保持栈内元素按单调递增或单调递减的顺序排列。这种看似简单的约束条件，却能高效解决一系列看似复杂的区间极值问题。从”柱状图中最大的矩形”到”每日温度”，从”下一个更大元素”到”接雨水”，单调栈在算法面试与实际工程中都有着极为广泛的应用。本文用Java完整实现单调栈的核心逻辑，深入讲解其”以空间换时间”的设计思想，并通过多个经典案例演示如何运用单调递增栈与单调递减栈解决实际问题。
一、单调栈的本质：维护有序区间信息
普通栈只关心后进先出（LIFO），而单调栈在此基础上增加了一条关键约束：栈内元素必须保持单调性（递增或递减）。这意味着每次入栈前，需要将破坏单调性的栈顶元素弹出，从而确保栈内始终有序。
1.1 为什么单调性能带来效率提升
以”寻找数组中每个元素的下一个更大元素”为例：
- 暴力解法：对每个元素向后扫描，最坏情况下时间复杂度为 O(n²)。
- 单调递减栈：利用栈维护一个”候选更大元素”的集合。当前元素入栈时，所有比它小的栈顶元素立刻找到”下一个更大元素”——就是当前元素本身。每个元素最多入栈一次、出栈一次，时间复杂度降至 O(n)。
这种”一次遍历、即时结算”的思想，是单调栈的核心优势。
1.2 单调递增栈 vs 单调递减栈
| 类型 | 栈内顺序 | 典型应用场景 |
|---|---|---|
| 单调递增栈 | 从栈底到栈顶递增 | 寻找下一个更小元素、柱状图最大矩形 |
| 单调递减栈 | 从栈底到栈顶递减 | 寻找下一个更大元素、每日温度、接雨水 |
选择递增还是递减，取决于问题要求的是”下一个更大”还是”下一个更小”。
二、核心实现：通用单调栈框架
下面是一个通用的单调递减栈框架，支持寻找每个元素的”下一个更大元素”（Next Greater Element, NGE）。
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
/**
* 单调栈通用框架与经典问题求解
* 核心思想：维护栈内单调性，利用O(n)时间解决区间极值问题
*/
public class MonotonicStack {
/**
* 问题1：下一个更大元素 I（经典模板）
* 给定数组nums，返回数组answer，其中answer[i]是nums[i]的下一个更大元素。
* 如果不存在，则返回-1。
*
* 算法思路（单调递减栈）：
* 1. 从左到右遍历数组
* 2. 当前元素为"审判者"，栈中元素是等待被审判的"嫌疑人"
* 3. 当前元素 > 栈顶元素 → 栈顶元素的NGE就是当前元素，出栈并记录
* 4. 当前元素 <= 栈顶元素 → 当前元素入栈，等待后面的更大元素
* 5. 遍历结束后，栈中剩余元素都没有NGE，记为-1
*
* 时间复杂度：O(n) — 每个元素最多入栈出栈各一次
* 空间复杂度：O(n) — 栈的空间
*/
public static int[] nextGreaterElement(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1); // 默认没有下一个更大元素
// 栈中存储的是数组下标，便于同时获取值和位置
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
// 关键循环：当前元素大于栈顶元素时，栈顶找到NGE
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
int idx = stack.pop(); // 栈顶元素出栈
result[idx] = nums[i]; // 记录NGE
}
// 当前元素入栈，等待后续元素来"审判"
stack.push(i);
}
// 栈中剩余元素没有NGE，保持默认值-1
return result;
}
/**
* 问题2：每日温度
* 给定温度数组，返回数组answer，answer[i]表示第i天之后需要等待多少天
* 才能遇到更高的温度。如果不存在，返回0。
*
* 与NGE的区别：这里需要记录的是"距离"而非"值"
*/
public static int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] answer = new int[n];
Deque<Integer> stack = new ArrayDeque<>(); // 存储下标
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int prevIdx = stack.pop();
answer[prevIdx] = i - prevIdx; // 记录距离而非值
}
stack.push(i);
}
// 剩余元素没有更高温度，保持默认0
return answer;
}
/**
* 问题3：柱状图中最大的矩形（面试高频难题）
* 给定n个非负整数表示柱状图的高度，每个柱子的宽度为1，求能勾勒出的最大矩形面积。
*
* 核心洞察：
* 对于每个柱子i，以其高度为矩形的高时，矩形的左右边界分别是什么？
* - 左边界：左边第一个高度小于heights[i]的柱子
* - 右边界：右边第一个高度小于heights[i]的柱子
* - 矩形宽度 = rightBound - leftBound - 1
*
* 单调递增栈恰好能高效找到这两个边界！
*/
public static int largestRectangleArea(int[] heights) {
int n = heights.length;
// 技巧：在数组首尾添加高度为0的哨兵，简化边界处理
int[] newHeights = new int[n + 2];
System.arraycopy(heights, 0, newHeights, 1, n);
// 首尾哨兵已经是默认值0
int maxArea = 0;
Deque<Integer> stack = new ArrayDeque<>(); // 单调递增栈（存储下标）
for (int i = 0; i < newHeights.length; i++) {
// 当前高度 < 栈顶高度 → 栈顶柱子的右边界确定
while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
int height = newHeights[stack.pop()]; // 矩形的高度
int width = i - stack.peek() - 1; // 右边界i - 左边界stack.peek() - 1
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}
/**
* 问题4：接雨水（双指针与单调递减栈两种解法）
* 给定n个非负整数表示每个柱子的宽度为1的高度图，计算能接多少雨水。
*
* 单调递减栈解法思路：
* 栈中维护递减的高度，当遇到更高的柱子时，栈顶与次栈顶之间可以形成凹槽接水。
*/
public static int trap(int[] height) {
int water = 0;
Deque<Integer> stack = new ArrayDeque<>(); // 单调递减栈
for (int i = 0; i < height.length; i++) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int bottom = height[stack.pop()]; // 凹槽底部高度
if (stack.isEmpty()) break; // 没有左边界，无法接水
int leftBound = stack.peek();
// 当前凹槽能接的水 = 宽度 × 有效高度
int width = i - leftBound - 1;
int boundedHeight = Math.min(height[leftBound], height[i]) - bottom;
water += width * boundedHeight;
}
stack.push(i);
}
return water;
}
/**
* 问题5：下一个更大元素 II（循环数组版本）
* 数组是循环的，即nums[-1] == nums[n-1], nums[n] == nums[0]
* 技巧：将数组虚拟扩展一倍（不实际创建，用取模访问）
*/
public static int[] nextGreaterElementsII(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>();
// 遍历2n次，模拟循环数组
for (int i = 0; i < 2 * n; i++) {
int idx = i % n;
while (!stack.isEmpty() && nums[idx] > nums[stack.peek()]) {
result[stack.pop()] = nums[idx];
}
// 只有第一轮才将元素入栈
if (i < n) {
stack.push(idx);
}
}
return result;
}
}
三、关键代码解读：为什么这个while循环如此精妙
3.1 双重循环的O(n)之谜
单调栈的实现中，外层是一个 for 循环，内层是一个 while 循环。初看似乎是 O(n²)，但实质是 O(n)：
for (int i = 0; i < n; i++) { // 每个元素i只入栈一次
while (!stack.isEmpty() && condition) {
stack.pop(); // 每个元素只出栈一次
}
stack.push(i);
}
每个元素最多被 push 一次、pop 一次，因此总的操作次数不超过 2n。
3.2 哨兵技巧的妙用
在”柱状图最大矩形”中，我们在数组首尾各添加了一个高度为0的哨兵：
int[] newHeights = new int[n + 2];
System.arraycopy(heights, 0, newHeights, 1, n);
这解决了两个边界问题：
– 左哨兵（下标0）：确保栈中始终有元素，避免 stack.peek() 为空时的特殊判断。
– 右哨兵（下标n+1）：强制所有剩余元素在遍历结束时出栈，确保不会遗漏任何柱子的面积计算。
3.3 接雨水中的凹槽计算
接雨水是单调栈最具几何直觉的应用。当当前柱子 height[i] 大于栈顶时，弹出栈顶作为凹槽底部，新的栈顶变为左边界，当前柱子为右边界：
| 右边界 height[i]
| |‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾|
| | 雨水 |
左边界 |_____|_________________|_____
栈顶 弹出的底部
有效高度 = min(左边界高度, 右边界高度) - 底部高度，宽度 = 右边界下标 - 左边界下标 - 1。
四、完整测试与运行
public class MonotonicStackDemo {
public static void main(String[] args) {
MonotonicStack solver = new MonotonicStack();
// 测试1：下一个更大元素
int[] nums1 = {2, 1, 2, 4, 3};
System.out.println("=== 下一个更大元素 ===");
System.out.println("输入: " + Arrays.toString(nums1));
System.out.println("输出: " + Arrays.toString(solver.nextGreaterElement(nums1)));
// 期望: [4, 2, 4, -1, -1]
System.out.println();
// 测试2：每日温度
int[] temps = {73, 74, 75, 71, 69, 72, 76, 73};
System.out.println("=== 每日温度 ===");
System.out.println("输入: " + Arrays.toString(temps));
System.out.println("输出: " + Arrays.toString(solver.dailyTemperatures(temps)));
// 期望: [1, 1, 4, 2, 1, 1, 0, 0]
System.out.println();
// 测试3：柱状图最大矩形
int[] heights = {2, 1, 5, 6, 2, 3};
System.out.println("=== 柱状图最大矩形 ===");
System.out.println("输入: " + Arrays.toString(heights));
System.out.println("输出: " + solver.largestRectangleArea(heights));
// 期望: 10（以高度5和6的柱子为边界的矩形，宽度2，高度5，面积10）
System.out.println();
// 测试4：接雨水
int[] trapHeights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
System.out.println("=== 接雨水 ===");
System.out.println("输入: " + Arrays.toString(trapHeights));
System.out.println("输出: " + solver.trap(trapHeights));
// 期望: 6
System.out.println();
// 测试5：循环数组的下一个更大元素
int[] circular = {1, 2, 1};
System.out.println("=== 循环数组下一个更大元素 ===");
System.out.println("输入: " + Arrays.toString(circular));
System.out.println("输出: " + Arrays.toString(solver.nextGreaterElementsII(circular)));
// 期望: [2, -1, 2]
}
}
五、单调栈的适用场景总结
| 问题类型 | 判断特征 | 使用栈类型 |
|---|---|---|
| 下一个更大/更小元素 | 数组中找最近的大/小值 | 单调递减/递增栈 |
| 区间最值问题 | 以某元素为极值的最宽区间 | 单调递增栈 |
| 接雨水/面积问题 | 需要找到左右边界形成凹槽 | 单调递减栈 |
| 股票价格跨度 | 之前连续小于等于当前价格的天数 | 单调递减栈 |
| 去除重复字母/字典序 | 保持相对顺序的前提下优化 | 单调栈 + 访问标记 |
六、复杂度对比与算法选型
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力枚举 | O(n²) | O(1) | 数据量极小或作为验证 |
| 单调栈 | O(n) | O(n) | 寻找”下一个”或”最近”的更大/更小元素 |
| 线段树/RMQ | O(n log n) 预处理, O(log n) 查询 | O(n) | 多次任意区间查询 |
单调栈的优势在于单次线性扫描，不需要预处理，特别适合”流式数据”或只需要遍历一次的场景。
七、总结
单调栈的精髓不在于栈本身，而在于它维护的单调性约束所带来的信息压缩能力。当我们把数组元素压入栈时，实际上是在构建一个”候选答案”的层次结构；当元素被弹出时，它的”命运”已经被确定——它找到了它一直在等待的那个更大（或更小）的元素。
掌握单调栈，关键在于理解三个问题：入栈什么（通常是下标，因为需要计算距离）、何时出栈（当前元素破坏单调性时）、出栈后做什么（记录答案、计算面积、累加雨水）。这套思维框架一旦建立，你就能在面试中从容应对各类区间极值问题。
