题目:
AcWing 830. 单调栈:https://www.acwing.com/problem/content/832/
B:https://codeforces.com/gym/105158
解决问题:
得到一个数左边或右边第一个≥(>)或≤(<)它的数
模板:
// AcWing 830. 单调栈
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int arr[N], v[N], sta[N];
// 栈顶 sta[cnt]
// 入栈 sta[++ cnt] = input;
// 出栈 output = sta[cnt --];
// 栈是否为空 if !cnt <=> if sta.empty()
int cnt = 0;
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; ++ i)
scanf("%d",&arr[i]);
for(int i = n; i >= 1; -- i)
{
if(!cnt || arr[i] >= arr[sta[cnt]])
sta[++ cnt] = i;
else
{
while(cnt && arr[i] < arr[sta[cnt]])
v[sta[cnt --]] = arr[i];
sta[++ cnt] = i;
}
}
while(cnt)
v[sta[cnt --]] = -1;
for(int i = 1; i <= n; ++ i)
printf("%d ",v[i]);
return 0;
}
标签:cnt,sta,int,++,arr,--,单调
From: https://www.cnblogs.com/Frodnx/p/18406840