单调栈

Dec 16, 2024 11:43 AM
Dec 17, 2024 4:34 AM

题目描述

给出项数为 n 的整数数列 a1n

1n3×1061ai109

定义函数 f(i) 代表数列中第 i 个元素之后第一个大于 ai 的元素的下标,即 f(i)=mini<jn,aj>ai{j}。若不存在,则 f(i)=0

试求出 f(1n)

Solution

这个基础算法经常困住我,必须解决掉

倒着遍历:

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), f(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    vector<int> stk;
    for (int i = n;i >= 1;i--) {
        while (stk.size() && a[i] >= a[stk.back()]) stk.pop_back();
        if (stk.size())f[i] = stk.back();
        stk.push_back(i);
    }
    for (int i = 1;i <= n;i++)cout << f[i] << " ";
}

正着遍历:

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), f(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    vector<int> stk;
    for (int i = 1;i <= n;i++) {
        while (stk.size() && a[i] > a[stk.back()])f[stk.back()] = i, stk.pop_back();
        stk.push_back(i);
    }
    for (int i = 1;i <= n;i++)cout << f[i] << " ";
}