单调栈是指栈内元素保持单调递增或单调递减的栈结构，在寻找变量序列中下一个更大值的问题里，我们通常使用单调递增栈，栈底到栈顶的元素值依次增大，这样可以在遍历序列的过程中快速匹配每个元素右侧第一个比它大的元素。
单调栈解决下一个更大值的核心思路
遍历目标序列时，对于每个当前元素，我们不断检查栈顶元素对应的值是否小于当前元素的值：如果是，那么当前元素就是栈顶元素对应的下一个更大值，弹出栈顶元素并记录结果；如果不是，就将当前元素的索引压入栈中。这样遍历完成后，栈中剩余的元素就是没有下一个更大值的元素，结果中可以标记为-1或者对应场景的默认值。
这种方式的优势在于每个元素只会入栈和出栈各一次，整体时间复杂度为O(n)，空间复杂度为O(n)，比暴力解法的O(n²)时间复杂度要高效很多。
基础实现示例（以数组为例）
下面是一个寻找整型数组中每个元素下一个更大值的基础实现，使用Java语言编写：
import java.util.Arrays;
import java.util.Stack;
public class NextGreaterElement {
public static int[] findNextGreater(int[] nums) {
int n = nums.length;
int[] result = new int[n];
// 初始化结果数组，默认值为-1表示没有下一个更大值
Arrays.fill(result, -1);
Stack<Integer> stack = new Stack<>();
// 遍历数组
for (int i = 0; i < n; i++) {
// 当栈不为空，且当前元素大于栈顶索引对应的元素时
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
int prevIndex = stack.pop();
result[prevIndex] = nums[i];
}
// 将当前索引压入栈
stack.push(i);
}
return result;
}
public static void main(String[] args) {
int[] testNums = {2, 1, 2, 4, 3};
int[] res = findNextGreater(testNums);
for (int num : res) {
System.out.print(num + " ");
}
// 输出结果：4 2 4 -1 -1
}
}
循环数组场景的适配
如果序列是循环数组，也就是数组末尾元素的下一个更大值可能在数组开头，我们只需要在遍历的时候把数组遍历两遍即可，索引通过取模的方式获取对应元素：
import java.util.Arrays;
import java.util.Stack;
public class CircularNextGreater {
public static int[] findCircularNextGreater(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Stack<Integer> stack = new Stack<>();
// 遍历两倍数组长度，处理循环场景
for (int i = 0; i < 2 * n; i++) {
int num = nums[i % n];
while (!stack.isEmpty() && num > nums[stack.peek()]) {
int prevIndex = stack.pop();
result[prevIndex] = num;
}
// 只在第一遍遍历的时候压入索引，避免重复入栈
if (i < n) {
stack.push(i);
}
}
return result;
}
public static void main(String[] args) {
int[] testNums = {1, 2, 1};
int[] res = findCircularNextGreater(testNums);
for (int num : res) {
System.out.print(num + " ");
}
// 输出结果：2 -1 2
}
}
适用场景与注意事项
单调栈寻找下一个更大值的场景非常广泛，除了基础的数组元素匹配，还可以用于：
- 温度序列中等待升温的天数计算
- 柱状图中最大矩形的边界判断
- 每日股票价格的下一个更高价格匹配
使用时需要注意几个点：第一，栈中存储的通常是元素的索引而不是元素值，这样方便我们同时获取元素值和对应位置；第二，单调递增栈用于找下一个更大值，单调递减栈则用于找下一个更小值，不要混淆栈的单调性方向；第三，处理循环场景时需要注意遍历次数和索引的取模逻辑，避免出现结果错误。