#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
using namespace std;
class Solution
{
public:
    int bestRotation(vector<int> &nums)
    {
        // points数组表示每一种k对应的nums[i]的偏移k后的得分
        int n = nums.size();
        vector<int> points(n, 0);
        vector<int> d(n, 0); //差分数组 d[i]=points[i]-points[i-1]
        for (int i = 0; i < n; i++)
        {
            //对于points数组，如果需要将[i,j]范围内的所有得分+1
            //则可以修改差分数组范围一左一右的d[i],d[j+1],前者+1,后者-1
            int left = (i + 1) % n, right = (i - (nums[i] - 1) + n) % n;
            //上述两个就相当于修改差分数组的d[i]与d[j+1]
            d[left]++;
            d[right]--;
            //另外需要注意的是，对于循环偏移，如果是将第一个移动到了末尾
            //则一定会+1
            if (left >= right)
                d[0]++;
        }
        //查找维护结果
        int sum = 0, max = -1, ans = 0;
        for (int i = 0; i < n; i++)
        {
            if ((sum += d[i]) > max)
            {
                max = sum;
                ans = i;
            }
        }
        return ans;
    }
};
int main()
{
    Solution *s = new Solution();
    vector<int> nums{2, 3, 1, 4, 0};
    int result = 0;
    result = s->bestRotation(nums);
    cout << "result = " << result << endl;
    return 0;
}