AcWing 4983. 最大的数 (单调栈)
原题链接
中等
作者:
Suzukie
,
2023-08-08 21:25:48
,
所有人可见
,
阅读 72
单调栈 从后往前枚举 栈维持右边最大的数
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N];
int stk[N];
int top = -1;
int main()
{
int n;
cin >> n;
for(int i = 0;i < n;i ++)scanf("%d",&a[i]);
for(int i = n-1;i >= 0;i --)
{
if(top == -1)b[i] = 0;
if(stk[top] < a[i])b[i] = 0;
else if(top != -1) b[i] = stk[top] - a[i] + 1;
if(top == -1 || a[i] > stk[top]) stk[++top] = a[i];
}
for(int i = 0;i < n;i ++)printf("%d ",b[i]);
}