LeetCode每日一题：LeetCode 798. 得分最高的最小轮调

LeetCode 798. 得分最高的最小轮调

不等式推到出每个数论调不加分的区间，如果最后累加的不加分区间最少，那就是论调加分最多。通过差分数组维护不加分的区间。
不等式推到如下：
$i-k<a[i]$ && $0<=i-k<=n-1$
得出范围为：$i-a[i]+1<=kandk<=i$

class Solution {
public:
    int bestRotation(vector<int>& A) {
        int n = A.size();
        vector<int> b(n + 1);
        for (int i = 0; i < n; i ++ ) {
            int l = i - A[i] + 1, r = i;
            if (l >= 0) {
                b[l] ++ , b[r + 1] --;
            }
            else {
                b[0] ++ , b[r + 1] -- ;
                b[l + n] ++ , b[n] -- ;
            }
        } 

        int res = INT_MAX, k = 0;
        for (int i = 0, sum = 0; i < n; i ++ ) {
            sum += b[i];
            if (sum < res) {
                res = sum;
                k = i;
            }
        }
        return k;
    }
};