798.得分最高的最小轮调

链接：798.得分最高的最小轮调
难度：Hard
标签：数组、前缀和
简介：在所有可能的轮调中，返回我们所能得到的最高分数对应的轮调下标 k 。如果有多个答案，返回满足条件的最小的下标 k 。

题解 1 - cpp

• 编辑时间：2022-03-09
• 执行用时：92ms
• 内存消耗：70.1MB
• 编程语言：cpp
• 解法介绍：统计每个点可实现的 k 区间，利用差分加速。

class Solution {
   public:
    int list[100001] = {0};
    int bestRotation(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (i >= nums[i]) {
                list[0]++;
                list[i - nums[i] + 1]--;
            }
            list[i + 1]++;
            list[min(i + n - nums[i] + 1, n)]--;
        }
        int ans = 0, ansnum = 0, sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += list[i];
            if (sum > ansnum) {
                ans = i;
                ansnum = sum;
            }
        }
        return ans;
    }
};