题目链接：798. 得分最高的最小轮调
暴力解法需要 $O(n^2)$ 的时间复杂度，会超时。
每个元素都有一个可以得分的 $k$ 的区间，该区间为 $[(i + 1) \% N, (i + 1 - n_i + N) \% N]$，其中 $N$ 为数组长度，$n_i$ 是数组中第 $i$ 个元素。
使用『差分』操作，可以以 $O(1)$ 时间复杂度标记『区间修改』，并且以 $O(n)$ 时间复杂度，进行『单点查询』。求前缀和后，就可以以 $O(1)$ 的时间复杂度进行『单点查询』。
找标记次数最多的位置可对差分数组求前缀和再进行遍历即可。
from typing import List
class Solution:
def bestRotation(self, nums: List[int]) -> int:
diffs = [0] * len(nums)
def add(l: int, r: int):
diffs[l] += 1
diffs[r + 1] -= 1
for i, n in enumerate(nums):
lower, upper = (i + 1) % len(nums), (i + 1 - n + len(nums)) % len(nums)
diffs[lower] += 1
diffs[upper] -= 1
if lower >= upper:
diffs[0] += 1
score, best_score, best_k = 0, 0, 0
for i, diff in enumerate(diffs):
score += diff
if score > best_score:
best_score, best_k = score, i
return best_k