题目描述

给定一个数组 A，我们可以将它按一个非负整数 K 进行轮调，这样可以使数组变为 A[K], A[K+1], A[K+2], ... A[A.length - 1], A[0], A[1], ..., A[K-1] 的形式。此后，任何值小于或等于其索引的项都可以记作 1 分。

例如，如果数组为 [2, 4, 1, 3, 0]，我们按 K = 2 进行轮调后，它将变成 [1, 3, 0, 2, 4]。这将记作 3 分，因为 1 > 0 [没有得分], 3 > 1 [没有得分], 0 <= 2 [1 分], 2 <= 3 [1 分], 4 <= 4 [1 分]。

在所有可能的轮调中，返回我们所能得到的最高分数对应的轮调索引 K。如果有多个答案，返回满足条件的最小的索引 K。

样例

输入：[2, 3, 1, 4, 0]
输出：3
解释：
下面列出了每个 K 的得分：
K = 0,  A = [2,3,1,4,0],    score 2
K = 1,  A = [3,1,4,0,2],    score 3
K = 2,  A = [1,4,0,2,3],    score 3
K = 3,  A = [4,0,2,3,1],    score 4
K = 4,  A = [0,2,3,1,4],    score 3
所以我们应当选择 K = 3，得分最高。

输入：[1, 3, 0, 2, 4]
输出：0
解释：
A 无论怎么变化总是有 3 分。
所以我们将选择最小的 K，即 0。

提示

• A 的长度最大为 20000。
• A[i] 的取值范围是 [0, A.length]。

算法

(区间标记) $O(n)$

1. 对于每个数字，求出其能得分的轮调区间。比如样例 1 中下标为 1 位置的数字 3，其能得分的轮调区间为 [2, 3]。再比如下标为 2 的数字 1，其能得分的区间有两段，分别为 [0, 1] 和 [3, 4]。
2. 具体地，每个数字最多有两段能得分的区间。假设数组长度为 n，对于在下标为 i 位置的数字 A[i]，如果 A[i] >= n，则得分区间不存在；在 A[i] < n 的情况下，如果 A[i] > i，则得分区间为 [i + 1, i + n - A[i]]；如果 A[i] < i，则得分区间为 [0, i - A[i]] 和 [i + 1, n - 1]。
3. 得到了每个数的合法区间，我们通过区间标记的方法求出得分最大的点。如果 [l, r] 是一个得分区间，则我们标记 valid[l]++ 且 valid[r + 1]--，然后求出 valid 数组的前缀和。数组中最大值的点就是得分最大的点。

时间复杂度

• 标记区间时间复杂度为 $O(n)$，求最大值时间复杂度也为 $O(n)$，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间记录标记。

C++ 代码

class Solution {
public:
    int bestRotation(vector<int>& A) {
        int n = A.size();
        vector<int> valid(n + 1, 0);

        for (int i = 0; i < n; i++) {
            if (A[i] >= n)
                continue;
            if (A[i] > i) {
                valid[i + 1]++;
                valid[i + n - A[i] + 1]--;
            } else {
                valid[0]++;
                valid[i - A[i] + 1]--;
                valid[i + 1]++;
                valid[n]--;
            }
        }

        int ans = valid[0], ansi = 0;
        for (int i = 1; i < n; i++) {
            valid[i] += valid[i - 1];
            if (ans < valid[i]) {
                ans = valid[i];
                ansi = i;
            }
        }

        return ansi;
    }
};