题目描述
算法1
(后缀) $O(n)$
从后道前类似前缀和算后缀最大值,然后有最大值-$a_i$的差值为答案
C++ 代码
#include <iostream>
using namespace std;
const int N = 100010;
int n, a[N], f[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = n; i >= 1; i -- ) f[i] = max(f[i + 1], a[i]);
for (int i = 1; i <= n; i ++ )
{
printf("%d ", max(0, f[i + 1] - a[i] + 1)); //i+1~n的最大数-a[i]
}
return 0;
}