AcWing 830. 单调栈
原题链接
简单
作者:
NCpaste
,
2023-05-25 13:42:30
,
所有人可见
,
阅读 22
思路
注意
- 题目给的条件是小于,所以大于等于分一类,注意区分等号情况的位置
#include <iostream>
using namespace std;
const int N = 1e5;
int a[N];
int b[N];
int main ()
{
int n;
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> a[i];
}
a[0] = -1;
for (int i = 1; i <= n; i ++)
{
int t = i-1;
if (a[i] > a[t])
{
b[i] = a[t];
}
else
{
while(a[i] <= b[t])
{
t --;
}
b[i] = b[t];
}
}
for (int i = 1; i <= n; i ++)
{
cout << b[i] << " ";
}
cout << endl;
return 0;
}
/*
10
11 27 11 6 14 26 8 22 13 7
-1 11 -1 -1 6 14 6 8 8 6
-1 11 11 -1 6 14 6 8 8 6
*/