acwing-830. 单调栈

给定一个长度为 N 的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1。

输入格式

第一行包含整数 N,表示数列长度。

第二行包含 N 个整数,表示整数数列。

输出格式

共一行,包含 N 个整数,其中第 i 个数表示第 i 个数的左边第一个比它小的数,如果不存在则输出 −1。

数据范围

1≤N≤105
1≤数列中元素≤109

输入样例:

5
3 4 2 7 5

输出样例:

-1 3 -1 2 2

方法一:

单调栈模板题

思路:

首先对于输入数列中任意数x,其左边任何比x大的数肯定不会被输出,即不需要保存下来,因为对于x右边的数(即在x之后输入的数),他们左边的第一个比他们最小的数肯定轮不到x左边那些比x大的数

做法:

维护一个数组将已读入的数保存起来,在读入下一个数的时候,若左边离其最近的数大于/等于他,就将其从数组中删除,直到数组为空或左边第一个不是大于/等于他的数,然后将其保存到数组。上述操作就是维护一个单调递增的栈

看起来有回溯,但复杂度是O(n),因为对于每个数,都一次输入和一次可能被回溯并删除的机会,不会被回溯多次

#include <bits/stdc++.h>

using namespace std;

int n;
int st[100010];

int main() {
    int x, t = -1;
    cin >> n;
    while (n--) {
        cin >> x;
        while (t >= 0 && st[t] >= x) t--;
        cout << (t >= 0 ? st[t] : -1) << " ";
        st[++t] = x;
    }
}
上一篇:BZOJ 3942: [Usaco2015 Feb]Censoring


下一篇:ST意法半导体