单调栈：在线性时间内寻找最近更大元素｜算法讲义

问题#

给定数组 $a$ 。对每个位置 $i$ ，寻找它右侧第一个满足 $a_j>a_i$ 的位置 $j$ ；若不存在则返回 $-1$ 。

直接从每个位置向右扫描，最坏需要 $O(n^2)$ 时间。单调栈把“还没有找到答案的位置” 保留下来，让每个下标最多进栈、出栈各一次。

核心思想#

从左向右扫描数组，栈中存放尚未找到右侧严格更大元素的下标。遇到新元素 $a_i$ 时：

当栈顶对应的值严格小于 $a_i$ ， $i$ 就是栈顶位置的第一个更大元素。
弹出栈顶并记录答案，继续检查新的栈顶。
最后把 $i$ 入栈，等待未来的更大元素。

不变量#

栈内下标严格递增，因为它们按扫描顺序入栈。
从栈底到栈顶，对应值单调不增。
栈中每个下标在已经扫描的区间内都没有更大元素。

为什么弹出时得到的是“第一个”更大元素？如果在 $i$ 之前存在更大的位置，该下标早已在处理那个位置时出栈，不可能一直留到现在。

对于“严格更大”，弹栈条件必须是 a[stack.back()] < a[i]。相等元素不能互相作为答案。

复杂度#

虽然代码中有嵌套的 while，但每个下标只会入栈一次、出栈一次：

时间： $O(n)$
额外空间： $O(n)$

可独立编译的 C++17 模板#

输入第一行是 $n$ ，第二行是 $n$ 个整数。输出每个位置右侧第一个严格更大元素的 0-based 下标，不存在则输出 $-1$ 。

#include <cstddef>
#include <iostream>
#include <vector>

std::vector<int> next_greater_index(
    const std::vector<long long>& values
) {
    const int n = static_cast<int>(values.size());
    std::vector<int> answer(n, -1);
    std::vector<int> stack;
    stack.reserve(values.size());

    for (int i = 0; i < n; ++i) {
        while (
            !stack.empty() &&
            values[static_cast<std::size_t>(stack.back())] <
                values[static_cast<std::size_t>(i)]
        ) {
            answer[static_cast<std::size_t>(stack.back())] = i;
            stack.pop_back();
        }
        stack.push_back(i);
    }

    return answer;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0;
    std::cin >> n;
    if (n < 0) {
        return 0;
    }

    std::vector<long long> values(static_cast<std::size_t>(n));
    for (long long& value : values) {
        std::cin >> value;
    }

    const std::vector<int> answer = next_greater_index(values);
    for (std::size_t i = 0; i < answer.size(); ++i) {
        if (i != 0) {
            std::cout << ' ';
        }
        std::cout << answer[i];
    }
    std::cout << '\n';
}

示例#

输入：

5
2 1 2 4 3

输出：

3 2 3 -1 -1

位置 0 的值为 2，右侧第一个严格更大的值是位置 3 的 4。
位置 1 的值为 1，位置 2 的 2 就是答案。
位置 4 右侧没有元素。

易错点#

严格与非严格混淆：求“第一个大于等于”时，弹栈条件应改为 <=。
只存值不存下标：题目通常需要位置、距离或贡献，栈中应保存下标。
错误理解单调方向：本题栈中对应值单调不增；换成“更小元素”时方向相反。
弹栈后忘记继续比较：一个新元素可能同时解决多个旧位置。
把未出栈元素漏掉：答案数组应预先填为 $-1$ 。
用栈深度估算成 $O(n^2)$ ：应按总入栈、出栈次数做均摊分析。

边界测试#

空数组与单元素数组。
严格递增、严格递减、全部相等。
含重复平台，例如 2 2 3。
最大值位于中间或末尾。
负数与极大整数。
随机短数组，与逐位置向右暴力扫描的 $O(n^2)$ 实现对拍。

变体#

左侧第一个更大元素：仍从左向右扫描，但在当前元素入栈前直接读取栈顶。
最近更小元素：反转比较方向。
循环数组：扫描两遍，用下标对 $n$ 取模，第二遍通常不再入栈。
柱状图最大矩形：维护递增栈，在柱高下降时结算被弹出柱子的最大宽度。
元素贡献法：求每个元素作为区间最小值或最大值的覆盖范围，再累加贡献。重复值时，一侧使用严格比较、另一侧使用非严格比较，避免重复计数。