单调栈

题目描述

给出项数为 $n$ 的整数数列 $a_{1 \dots n}$ 。

$1 \leq n \leq 3 \times 10^{6}$ ， $1 \leq a_{i} \leq 10^{9}$ 。

定义函数 $f (i)$ 代表数列中第 $i$ 个元素之后第一个大于 $a_{i}$ 的元素的下标，即 $f (i) = min_{i < j \leq n, a_{j} > a_{i}} {j}$ 。若不存在，则 $f (i) = 0$ 。

试求出 $f (1 \dots n)$ 。

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] << " ";
}

Note

我更喜欢的是：往右侧遍历就正向遍历，否则倒着遍历。(这样会更加方便，少一个判断条件且判断条件都是严格的大于小于)

大致分为四种情况

往右侧寻找第一个比当前元素大的元素
往右侧寻找第一个比当前元素小的元素
往左侧寻找第一个比当前元素大的元素
往左侧寻找第一个比当前元素小的元素

对于 2 和 1 差不多，将>换为<即可

对于往左侧寻找：
3. 往左侧寻找第一个比当前元素大的元素

void solve() {
    vector<int> f(n, -1);
    vector<int> stk; // 存元素下标，栈内元素单调递减

    for (int i = 0; i < n; ++i) {
        while (!stk.empty() &&  a[i] >= a[stk.back()]) {
            stk.pop_back();
        }
        if (stk.size())f[i] = stk.back();
        stk.push_back(i);
    }
    return f;
}

若倒序？

void solve() {
    vector<int> f(n, -1);
    vector<int> stk; // 存元素下标，栈内元素单调递减

    for (int i = n; i >= 0; --i) {
        while (!stk.empty() &&  a[i] > a[stk.back()]) {
	        f[stk.back()] = i;
            stk.pop_back();
        }
        stk.push_back(i);
    }
    return f;
}

往左侧寻找第一个比当前元素小的元素

void solve() {
    vector<int> f(n, -1);
    vector<int> stk; // 存元素下标，栈内元素单调递增

    for (int i = 0; i < n; ++i) {
        while (!stk.empty() && a[i] <= a[stk.back()]) {
            stk.pop_back();
        }
        f[i] = stk.empty() ? -1 : a[stk.back()];
        stk.push_back(i);
    }
    return f;
}