单调栈

右侧第一个更大元素

给定数组 a，对每个下标 i 求右侧最小下标 j，使 j>i 且 a[j]>a[i]；若不存在，结果为 -1。输出为下标数组，可进一步转换为对应值或下标距离。数组元素不要求有序，比较关系限定为严格大于。

直接算法对每个位置向右扫描，遇到满足条件的元素后结束该次搜索。严格递减数组中，每个位置都需要检查其后全部元素，总比较次数为 n(n-1)/2，最坏时间复杂度为 O(n²)。

逐项扫描会反复访问相同的后缀。可以从左到右只扫一次，用栈保存还没找到答案的下标，每遇到一个新元素，就给栈中比它小的元素填上答案。

怎样维护栈

栈中保存尚未找到右侧更大元素的下标，下标按扫描顺序从栈底到栈顶递增，对应值保持非递增。处理新下标 i 时，只要 a[i] 严格大于栈顶值，就弹出该下标并将其答案设为 i；随后继续比较新的栈顶，最后将 i 压栈。

栈里保存下标，便能用 a[index] 比较值，用 answer[index] 写回答案。重复值也能分别处理。如果要求等待距离，就用答案下标减去原下标。

一个下标还留在栈里，说明此前扫描过的右侧元素都没让它出栈。扫描按下标顺序推进，因此让它出栈的当前元素就是右侧第一个更大元素。

栈底到栈顶的值非递增。当前值不大于栈顶时，也不大于栈内更下面的值，可以停止比较。弹出较小值后再压入当前下标，就能继续保持这个顺序。

题目要求严格大于，所以相等时不出栈。对于 [2,2,3]，两个 2 的答案都为下标 2，结果是 [2,2,-1]。如果用小于等于作为弹出条件，就变成查找右侧第一个大于等于的元素。

Java 实现

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

public class NextGreater {
    static int[] nextGreater(int[] a) {
        int[] answer = new int[a.length];
        Arrays.fill(answer, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < a.length; i++) {
            while (!stack.isEmpty() && a[stack.peek()] < a[i]) {
                answer[stack.pop()] = i;
            }
            stack.push(i);
        }
        return answer;
    }

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

保存为 NextGreater.java，使用 Java 21 运行。ArrayDeque 的 push、pop 和 peek 都操作同一端。答案预置为 -1，扫描结束后仍在栈中的位置保持 -1。空数组返回空数组，输入不能为 null。

数组 [2,1,2,4,3] 的结果是 [3,2,3,-1,-1]。最后下标 3、4 还在栈中，它们右侧没有更大元素。

为什么是线性时间

外层循环执行 n 次，每个下标入栈一次，最多出栈一次。虽然一次 while 可能弹出多个元素，但整趟扫描最多弹出 n 次，加上各轮的条件检查，总时间为 O(n)。

一个很大的元素可能一次弹空栈，但这些下标之后不会再次处理。这就是摊还分析：统计整个操作序列的总开销。最坏情况下所有下标都留在栈里，额外空间为 O(n)。

Java 示例的下标用了包装类型，有装箱和容器开销。数据量大时，可以改用 int 数组和栈顶指针，比较规则不变。

测试时覆盖空数组、全相等、严格递增、严格递减和连续出栈的情况，再用逐项向右扫描的算法核对随机短数组。

单调栈适合这类扫描中就能确定最终答案的问题。统计右侧所有更大元素的数量需要保存更多关系；动态修改会让已有答案失效；环形数组则需要调整扫描范围。