(单调栈) $O(n)$
思路分析
首先思考暴力做法, 枚举i:0->n
,枚举j:i-1->0
,a[1,2....n]
。如果设想将i左边的数存入栈中,要找
的是栈中第一个比a[i]
小的。存在这样一种情况:如果a[j]>=a[k]
,且j < k
,
那么第一个比a[i]
小的一定不是a[j]
,因为此时a[i]>a[j]>=a[k]
,且k>j
,而应该是a[k]
故可以将a[j]
排除。将满足这种情况的数都除去,此时栈中的数是单调的。
那么将比a[i]
大的栈顶元素弹出栈,直到栈顶元素小于a[i]
,此时这个栈顶元素就是左边第一个
比a[i]
小的,此后维护单调栈即可。
C++ 代码
#include <iostream>
using namespace std;
const int N = 100010;
int stk[N], tt;
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
while (tt && stk[tt] >= x) tt--;
if (tt) printf("%d ", stk[tt]);
else printf("-1 ");
stk[++tt] = x;
}
return 0;
}