这是 LeetCode 上的「798. 得分最高的最小轮调」,难度为「困难」。
Tag : 「区间求和问题」、「差分」
给你一个数组
,我们可以将它按一个非负整数
进行轮调,这样可以使数组变为
的形式。此后,任何值小于或等于其索引的项都可以记作一分。
例如,数组为
,我们按
进行轮调后,它将变成
。这将记为
分,因为
[不计分]、
[不计分]、
[计
分]、
[计
分],
[计
分]。在所有可能的轮调中,返回我们所能得到的最高分数对应的轮调下标
。如果有多个答案,返回满足条件的最小的下标
。
示例 1:
输入:nums = [2,3,1,4,0]
输出:3
解释:
下面列出了每个 k 的得分:
k = 0, nums = [2,3,1,4,0], score 2
k = 1, nums = [3,1,4,0,2], score 3
k = 2, nums = [1,4,0,2,3], score 3
k = 3, nums = [4,0,2,3,1], score 4
k = 4, nums = [0,2,3,1,4], score 3
所以我们应当选择 k = 3,得分最高。
示例 2:
输入:nums = [1,3,0,2,4]
输出:0
解释:
nums 无论怎么变化总是有 3 分。
所以我们将选择最小的 k,即 0。
提示:
为了方便,令
为
长度(中文的数据范围是错的,数组长度应该是
,不是
)。
对于给定的
而言,有效的轮调范围为
,即对于任意
而言,可取的下标共有
种。
假定当前下标为
,轮调次数为
,那么轮调后下标为
,当新下标为负数时,相当于
出现在比原数组更“靠后”的位置,此时下标等价于
。
考虑什么情况下
能够得分?
首先新下标的取值范围为
,即有
。由此可分析出
的取值范围为:
即由新下标取值范围可知
的上下界分别为
和
。
同时为了满足得分定义,还有
,进行变形可得:
此时我们有两个关于
的上界
和
,由于
取值范围为
,则有
,由于必须同时满足「合法移动(有效下标)」和「能够得分」,我们仅考虑范围更小(更严格)由
推导而来的上界
即可。
综上,
能够得分的
的取值范围为
。
最后考虑
(均进行加
模
转为正数)什么情况下为合法的连续段:
时,
为合法连续段;
时,根据负数下标等价于
,此时
等价于
和
两段。
至此,我们分析出原数组的每个
能够得分的
的取值范围,假定取值范围为
,我们可以对
进行
标记,代表范围为
能够得
分,当处理完所有的
后,找到标记次数最多的位置
即是答案。
标记操作可使用「差分」实现(不了解差分的同学,可以先看前置🧀:差分入门模板题,里面讲解了差分的两个核心操作「区间修改」&「单点查询」),而找标记次数最多的位置可对差分数组求前缀和再进行遍历即可。
代码:
class Solution {
static int N = 100010;
static int[] c = new int[N];
void add(int l, int r) {
c[l] += 1; c[r + 1] -= 1;
}
public int bestRotation(int[] nums) {
Arrays.fill(c, 0);
int n = nums.length;
for (int i = 0; i < n; i++) {
int a = (i - (n - 1) + n) % n, b = (i - nums[i] + n) % n;
if (a <= b) {
add(a, b);
} else {
add(0, b);
add(a, n - 1);
}
}
for (int i = 1; i <= n; i++) c[i] += c[i - 1];
int ans = 0, k = c[0];
for (int i = 1; i <= n; i++) {
if (c[i] > k) {
k = c[i]; ans = i;
}
}
return ans;
}
}
这是我们「刷穿 LeetCode」系列文章的第 No.798
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。