$O(n^2)$ 40 分

// O(n^2) 超时代码
#include <bits/stdc++.h>
using namespace std;
int n;
int a[200005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    long long ans = -1;
    // 以 a[mid] 作为最高点
    for (int mid = 1; mid <= n; mid++)
    {
        // left 次的左边某个数到 mid 的 +1 让左边递增
        // right 次的右边某个数到 mid 的 +1 让右边递减
        long long left = 0;
        long long right = 0;
        for (int i = 2; i <= mid; i++)
            if (a[i] <= a[i - 1])
                left += a[i - 1] - a[i] + 1;
        for (int i = mid; i <= n - 1; i++)
            if (a[i] <= a[i + 1])
                right += a[i + 1] - a[i] + 1;
        // 左右的区间 +1 可以衔接上
        long long now = max(left, right);
        if (ans == -1 || now < ans)
            ans = now;
    }
    cout << ans;
    return 0;
}

$O(n)$ 满分

// O(n)，预处理 left[],right[]
#include <bits/stdc++.h>
using namespace std;
int n;
int a[200005];
long long _left[200005];
long long _right[200005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // 预处理 left[],right[]
    _left[1] = 0;
    for (int i = 2; i <= n; i++)
        if (a[i] <= a[i - 1])
            _left[i] = _left[i - 1] + (a[i - 1] - a[i] + 1);
        else
            _left[i] = _left[i - 1];
    _right[n] = 0;
    for (int i = n - 1; i >= 1; i--)
        if (a[i] <= a[i + 1])
            _right[i] = _right[i + 1] + (a[i + 1] - a[i] + 1);
        else
            _right[i] = _right[i + 1];
    long long ans = -1;
    // 以 a[mid] 作为最高点
    for (int mid = 1; mid <= n; mid++)
    {
        // left 次的左边某个数到 mid 的 +1 让左边递增
        // right 次的右边某个数到 mid 的 +1 让右边递减
        long long now = max(_left[mid], _right[mid]);
        if (ans == -1 || now < ans)
            ans = now;
    }
    cout << ans;
    return 0;
}

动态调整最高点的做法

#include <bits/stdc++.h>
using namespace std;
long long n, a[200005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    // a[1] 作为最高点的答案
    long long left = 0;
    long long right = 0;
    for (int i = 2; i <= n; i++)
        if (a[i] >= a[i - 1])
            right += a[i] - a[i - 1] + 1;
    // 记录最小的答案
    long long ans = max(left, right);
    // 调整最高点，从 i-1 调整到 i
    for (int i = 2; i <= n; i++)
    {
        // 左边多了一个 a[i-1]~a[i] 需要递增
        if (a[i] <= a[i - 1])
            left += a[i - 1] - a[i] + 1;
        // 左边少了一个 a[i-1]~a[i] 递减的需求
        if (a[i] >= a[i - 1])
            right -= a[i] - a[i - 1] + 1;
        // 更新答案
        ans = min(ans, max(left, right));
    }
    cout << ans;
    return 0;
}