下一个更大元素

一句话算法

新来的大元素负责结算它左边所有比它小、且还没找到答案的位置。

问题模型

对每个位置 $i$，求右侧第一个满足 $a_j>a_i$ 的位置 $j$。不存在则输出 0。

完整讲解见单调栈。

核心直觉

栈中保存还没找到答案的位置。若当前值比栈顶大，当前下标就是栈顶位置的答案；弹出后继续尝试结算新的栈顶。

算法步骤

1. 初始化答案数组为 0，表示默认不存在右侧第一个更大元素。
2. 用栈保存“还没找到答案”的下标。
3. 从左到右枚举当前位置 i。
4. 当栈非空且 a[栈顶] < a[i] 时：
   • 当前 i 就是栈顶位置的右侧第一个更大元素；
   • 记录 ans[栈顶]=i；
   • 弹出栈顶，继续尝试结算新的栈顶。
5. 将 i 入栈，等待后续更大元素结算它。
6. 扫描结束后，栈中剩余位置没有答案，保持 0。

算法证明

核心不变量： 扫描到位置 i 前，栈中保存的下标都还没有在已扫描部分找到右侧第一个更大元素，且栈中对应值单调不增。

1. 弹栈正确。 若当前 a[i] 大于栈顶 a[j]，并且 j 之前没有被弹出，说明 $j+1$ 到 $i-1$ 中没有元素大于 a[j]。因此 i 是 j 右侧第一个更大元素。
2. 未弹出正确。 若栈顶 a[j] >= a[i]，当前元素不能成为 j 的答案，j 应继续等待。
3. 单调性保持。 弹出所有小于 a[i] 的栈顶后，再把 i 入栈，栈内值仍然单调不增。
4. 不漏答案。 每个位置在遇到第一个能弹出它的更大元素时立即结算；若一直没有被弹出，答案就是不存在。

因此算法能正确求出每个位置右侧第一个更大元素。

复杂度分析

每个下标最多入栈一次、出栈一次。

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

        #include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n + 1), ans(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 栈中保存还没有找到右侧第一个更大元素的位置。
    vector<int> st;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && a[st.back()] < a[i]) {
            ans[st.back()] = i;
            st.pop_back();
        }
        st.push_back(i);
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << (i == n ? '\n' : ' ');
    }
    return 0;
}
    

测试用例

输入：

5
1 4 2 3 5

输出：

2 5 4 5 0

经典例题

1. luogu-P5788

标准单调栈模板题。注意输出的是位置，不是值。

2. LeetCode 739

求右侧第一个更高温度的距离，结算时输出 i - top。

应用分类详解

下一个更大元素的本质是：新元素负责结算左侧所有被它第一次超过的候选。

一、右侧第一个更大/更小

• 典型模式： 对每个位置，求它右边第一个更大、更小、更高或更低的位置。
• 识别信号： 出现“右侧第一个”“下一个更大”“等待多少天才更高”。
• 核心建模： 栈中保存未结算下标，新元素满足条件时弹栈并记录答案。

二、左侧最近更大/更小

• 典型模式： 查询每个位置左边最近一个满足大小关系的位置。
• 识别信号： 出现“左侧第一个”“前面最近的更高建筑”。
• 核心建模： 从左到右扫描，先维护栈，再读取栈顶作为左侧最近候选。