洛谷-P5788 【模板】单调栈 题解

核心思想

使用一个 单调递减栈 来维护尚未找到“下一个更大元素”的元素下标。

• 遍历数组时，如果当前元素 a[i]大于 栈顶元素对应的值 a[top]，说明找到了栈顶元素的“下一个更大元素”，即 f(top) = i。
• 将栈顶弹出，并继续检查新的栈顶，直到栈空或栈顶对应值 ≥ 当前值。
• 最后将当前下标 i 入栈。

遍历结束后，栈中剩余的下标都没有找到更大的元素，对应答案为 0。

为什么用单调栈？

• 暴力做法是 O(n^2)，对于 n=3*10^6 显然超时。
• 单调栈可以在线性时间内解决该问题，时间复杂度为 O(n)，每个元素最多入栈和出栈一次。

代码详解（C++）

#include<iostream>
#include<stack>
#include<vector>
using namespace std;

int n;
vector<int> vec(3000001, 0);   // 存储原数组（1-indexed）
vector<int> ans(3000001, 0);   // 存储答案 f(i)

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

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> vec[i];

    stack<int> S;  // 存放下标，维护单调递减（按值）

    for (int i = 1; i <= n; i++) {
        // 当前元素 vec[i] 比栈顶元素大 → 找到栈顶的“下一个更大”
        while (!S.empty() && vec[i] > vec[S.top()]) {
            ans[S.top()] = i;  // 记录答案
            S.pop();           // 弹出已处理的下标
        }
        S.push(i);  // 当前下标入栈
    }

    // 栈中剩余元素没有更大的，答案为 0（初始化已为0，可省略）
    while (!S.empty()) {
        ans[S.top()] = 0;
        S.pop();
    }

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

复杂度分析

• 时间复杂度：O(n)每个元素入栈、出栈各一次。
• 空间复杂度：O(n)用于存储数组、答案和栈。