算法
(暴力枚举) $O(n)$
我们可以维护一个数组,$g[i]$表示从$w[i+1]$到$w[n]$的最大值,那么在i处的答案就是$max(0, g[i] - w[i])$.
C++ 代码
// codeforce每日一题 https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 2e5 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 1e9 + 7;
int n, m;
int w[N], g[N];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i];
int maxn = 0;
for(int i=n;i;i--)
{
g[i] = maxn;
maxn = max(maxn, w[i]);
}
for(int i=1;i<=n;i++){
cout<<max(0, g[i]-w[i]+1)<<" ";
}
return 0;
}