C++ 第47题：单调栈应用：寻找每个元素右侧第一个更大元素（Next Greater Element）

题目

编写程序，解决经典单调栈（Monotonic Stack）问题：给定一个长度为 N 的整数数组，寻找数组中每个元素右侧“第一个比它自身更大”的元素数值，若右侧不存在更大元素则填 -1。从暴力 O(N^2) 双重循环的瓶颈出发，利用单调递减栈在 O(N) 线性时间内一次性得出全量答案。

输入格式：无需外部输入（内置测试序列）。

输出格式：输出原数组与计算出的每个元素右侧第一个更大元素序列。

数据范围与约定：时间复杂度严格 O(N)，每个元素最多进出栈各一次。

思路与算法

1. 暴力算法的缺陷
外层枚举当前数，内层向右扫描，最坏情况（如单调递减数组 [5, 4, 3, 2, 1]）下耗时 O(N^2)。

2. 单调栈单调性维持
从右向左逆向扫描数组（或者正向扫描维护索引栈）。维持栈内元素自底向上严格单调递减：当新元素 nums[i] 准备入栈时，栈顶所有 <= nums[i] 的元素均被彻底淘汰弹栈（因为它们永远不可能作为左侧更远元素的第一个更大者），此时新的栈顶即为答案！

3. O(N) 均摊分析
虽然内层有 while 循环，但每个元素在整个流程中最多仅执行 1 次压栈与 1 次弹栈，总摊还操作步数严格 ≤ 2N。

完整程序

#include <iostream>
#include <vector>
#include <stack>

std::vector<int> nextGreaterElements(const std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> result(n, -1);
    std::stack<int> st; // 单调递减栈：存储元素数值

    // 从右往左逆序遍历
    for (int i = n - 1; i >= 0; --i) {
        // 弹出所有不大于当前元素的无用值
        while (!st.empty() && st.top() <= nums[i]) {
            st.pop();
        }

        // 栈顶即为右侧第一个更大元素
        if (!st.empty()) {
            result[i] = st.top();
        }

        // 当前元素入栈
        st.push(nums[i]);
    }

    return result;
}

int main() {
    std::vector<int> nums = {2, 7, 3, 5, 4, 6, 8};

    std::cout << "原数组序列:       ";
    for (int x : nums) std::cout << x << "  ";
    std::cout << "\n";

    std::vector<int> nge = nextGreaterElements(nums);

    std::cout << "右侧首个更大元素: ";
    for (int x : nge) std::cout << x << "  ";
    std::cout << "\n";

    return 0;
}

运行示例

输出：

原数组序列:       2  7  3  5  4  6  8  
右侧首个更大元素: 7  8  5  6  6  8  -1