57 lines
1.8 KiB
C++
57 lines
1.8 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
const int N = 100010;
|
||
int n;
|
||
int stk[N], tt;
|
||
|
||
|
||
//单调栈
|
||
void ddz() {
|
||
scanf("%d", &n);
|
||
for (int i = 0; i < n; i++) {
|
||
int x;
|
||
scanf("%d", &x);
|
||
//单调栈其实大多数就这一个应用,时间复杂度是O(N)，比暴力法优化了一个数量级
|
||
//while (tt) 是指栈不是空的
|
||
while (tt && stk[tt] >= x) tt--; //如果数组中有元素存在，并且从右向左走，还存比x大的数据，那么需要将这些比x大的数据弹出
|
||
//if(tt)是指栈不是空的
|
||
if (tt) printf("%d ", stk[tt]);
|
||
else printf("-1 ");
|
||
//再加入一个数据x
|
||
stk[++tt] = x;
|
||
}
|
||
}
|
||
|
||
int a[N];
|
||
|
||
//暴力做法
|
||
// 思考暴力作法的性质，我们可以用一个栈来存储i左边的所有元素，最开始栈是空的，当我们的i指针每往右边移动一下的话，我们就向栈中加入一个数
|
||
// 这样如果存在逆序对，那么前面的就一定不会输出出来。换句话说就不用入栈了，入了也没用。
|
||
// 这种思路，其实是因为要求：找到左边第一个比i小的（大的）元素j在什么地方，如果在j左边存在一个k，这个k比j大，那么就没有必要生存了。
|
||
void baoli() {
|
||
scanf("%d", &n);
|
||
for (int i = 0; i < n; i++) {
|
||
scanf("%d", &a[i]);
|
||
for (int j = i - 1; i >= 0; j--) {
|
||
if (a[i] > a[j]) {
|
||
printf("%d ", a[j]);
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
//单调栈
|
||
int main() {
|
||
//输入+输出重定向
|
||
freopen("../AcWing/N4/832.txt", "r", stdin);
|
||
//单调栈
|
||
ddz();
|
||
//暴力做法
|
||
//baoli();
|
||
//关闭文件
|
||
fclose(stdin);
|
||
return 0;
|
||
} |