算法刷题系列（四十二）：单调栈——维护最近的更大、更小候选

算法刷题系列（四十二）：单调栈——维护最近的更大、更小候选

题目问“每个位置右边第一个更大的元素在哪里”时，逐个向右扫描会在最坏情况下花费 O(n²)。单调栈保留尚未找到答案的候选索引；新元素一旦能回答栈顶位置的问题，就将它弹出并完成答案。

本文求每个元素右侧第一个严格更大元素的索引，不存在时为 -1。例如 [2, 1, 2, 4, 3] 的结果是 [3, 2, 3, -1, -1]。

从右向左扫描

从右往左处理 i。栈中放的是右侧、尚有可能成为答案的索引，且从栈底到栈顶对应值严格递减。

1. 若栈顶值 <= values[i]，它不可能是 i 的严格更大候选，也不可能成为更左边位置的更优候选，将其弹出。
2. 弹完后，栈顶若存在，就是右侧最近的更大值：被弹出的索引都不大于当前值，而剩下栈顶是从右侧开始遇到的第一个更大候选。
3. 将 i 入栈，供后续更左侧位置查询。

不变量：处理完某个位置后，栈只保存右侧未被支配的候选索引；值沿栈底到栈顶严格递减。每个索引最多入栈、出栈一次，因此全程线性。

Java 实现

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Main {
    static int[] nextGreaterIndex(int[] values) {
        if (values == null) throw new IllegalArgumentException("values must not be null");
        int n = values.length;
        int[] answer = new int[n];
        Arrays.fill(answer, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && values[stack.peek()] <= values[i]) {
                stack.pop();
            }
            if (!stack.isEmpty()) answer[i] = stack.peek();
            stack.push(i);
        }
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(nextGreaterIndex(new int[]{2, 1, 2, 4, 3})));
        // [3, 2, 3, -1, -1]
    }
}

Python 实现

def next_greater_index(values: list[int]) -> list[int]:
    if values is None:
        raise ValueError("values must not be None")
    answer = [-1] * len(values)
    stack: list[int] = []
    for i in range(len(values) - 1, -1, -1):
        while stack and values[stack[-1]] <= values[i]:
            stack.pop()
        if stack:
            answer[i] = stack[-1]
        stack.append(i)
    return answer

assert next_greater_index([2, 1, 2, 4, 3]) == [3, 2, 3, -1, -1]
assert next_greater_index([5, 4, 3]) == [-1, -1, -1]
assert next_greater_index([2, 2]) == [-1, -1]
assert next_greater_index([]) == []

如何改成其他邻近关系

右侧第一个严格更小元素：仍从右向左扫描，但弹出 >= values[i] 的候选。左侧问题可以从左向右扫描；要找最近更大时，在遇到新值后弹出不大于它的栈顶，再查询栈顶并压入当前索引。是否弹出相等值决定“严格”还是“允许相等”，不可混淆。

若题目只要更大元素的值，将答案索引映射为对应值即可；若要距离则使用 answer[i] - i。循环数组常用把数组逻辑上扫描两遍、只在第一遍记录答案的方式，但栈和取模边界要明确。

复杂度与常见错误

时间为 O(n)，答案数组与栈共需 O(n) 空间。容易出错的地方包括：把栈存成值却需要返回位置；把 <= 错写成 < 导致相等值被当成严格更大；先把当前索引压栈再找答案而得到自己；以及忘记将无答案位置初始化为 -1。严格画出扫描方向和不变量后，弹栈条件通常就能自然推出。

小结

单调栈不是为了维护整个数组的排序，而是只保留还可能成为答案的候选。当前元素把被支配的候选一次性淘汰，每个元素最多进出栈一次，于是把反复扫描压缩为 O(n)。