光与影的个人博客

NEUCoder

0%

lc798.得分最高的最小轮调

发表于 更新于 分类于 ，

798.得分最高的最小轮调

第一次写一点思路都没有，扣了半天最终放弃，直奔题解，发现题目主要有两个难点

  1. 从轮调位置角度考虑转换到每个元素位置考虑
    • 我的思路一直局限在从选k出发，如何计算出每个k位置的分数？怎么找到一种贪心或者动态规状态传递的方式
    • 没有从元素的角度出发，某个元素满足小于等于index时，k一定在某个范围内，所有元素决定的k的范围交集次数最多的就是最优解（表达不出来这种思维的转变）
  2. 如何记录最大交集次数？
    • 看完一半题解就想到创建一个数组，每计算出一个k的范围，就将范围内记录全部加一
    • 题解提供的差分数组思路”针不错”

如何计算k的范围，以index=i处元素为例分情况讨论（基本思路：轮调等价于数组开头一部分元素拼接到数组末尾或者末尾一部分元素拼接到数组开头）

  1. $i < nums[i]$ 即元素值大于索引，必须增大元素索引才能满足条件

    • 左边至少增加 $nums[i] - i$ ，也就意味着 轮调位置k必须在当前元素后面，且k后边元素个数必须大于等于当前元素左边至少要增加的元素,可得公式为 $ nums.length - k >= nums[i] - i$ ，得到k的范围为

  2. $i >= nums[i]$ 即索引值大于等于元素值，由于已经满足条件，可以如条件继续在左边增加元素（k在当前位置右边），或者从左边删掉一部分元素（k在当前位置左边）

    • 左边增加元素个数任意（k在当前位置右边），即k大于i时始终成立

    • 左边删除一定数量元素，即最多$ i - nums[i]$，

  • 最终第二种情况k范围为

差分数组理解：

  1. 差分数组元素定义为：differ[i] = nums[i] - nums[i - 1]，实际代表原数组的与前一个位置元素的差（可以理解为每个元素的参考都是前一个元素）
  2. 若要将原数组中某个区间内元素统一加某个值，在开始加 $differ[start] + number$，在结束后一个位置减 $differ[end + 1] - number$

如何更新差分数组：

  1. 只需要执行两种操作，区间的左边界 + 1，区间的右边界右边-1

  2. 两种情况的differ数组更新情况

    1. $i < nums[i]$
      • differ[i + 1] + 1，differ[nums.length-nums[i] + i + 1] - 1

    2. $i >= nums[i]$

      • differ[i + 1] + 1,右边界越界，不需要记录
      • differ[0] + 1, differ[i - nums[i] + 1] - 1

    3. $ (nums.length + i - nums[i]) % nums.length$ 可以等价与两个右边界情况

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int bestRotation(int[] nums) {
        int[] differ = new int[nums.length + 1];
        int tempLow;
        int tempHigh;
        for(int i = 0;i < nums.length;i++){
            tempLow = i + 1;
            // 精髓
            tempHigh = (nums.length + i - nums[i]) % nums.length;
            differ[tempLow]++;
            differ[tempHigh + 1]--;
            //左右双开区间
            if(nums[i] <= i){
                differ[0]++;
            }
        }
        for(int i = 1;i < differ.length;i++){
            differ[i] += differ[i - 1];
        }
        int score = differ[0];
        int result = 0;
        for(int i = 1;i < differ.length;i++){
            if(differ[i] > score){
                result = i;
                score = differ[i];
            }
        }

        return result;
    }
}