2530. 执行 K 次操作后的最大分数

2530. 执行 K 次操作后的最大分数

难度: 中等

来源: 每日一题 2023.10.18

---

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数 为 0 。

在一步 操作 中：

选出一个满足 0 <= i < nums.length 的下标 i ，
将你的 分数 增加 nums[i] ，并且
将 nums[i] 替换为 ceil(nums[i] / 3) 。
返回在 恰好 执行 k 次操作后，你可能获得的最大分数。

向上取整函数 ceil(val) 的结果是大于或等于 val 的最小整数。

示例 1：

输入：nums = [10,10,10,10,10], k = 5
输出：50
解释：对数组中每个元素执行一次操作。最后分数是 10 + 10 + 10 + 10 + 10 = 50 。
1
2
3

示例 2：

输入：nums = [1,10,3,3,3], k = 3
输出：17
解释：可以执行下述操作：
第 1 步操作：选中 i = 1 ，nums 变为 [1,4,3,3,3] 。分数增加 10 。
第 2 步操作：选中 i = 1 ，nums 变为 [1,2,3,3,3] 。分数增加 4 。
第 3 步操作：选中 i = 2 ，nums 变为 [1,1,1,3,3] 。分数增加 3 。
最后分数是 10 + 4 + 3 = 17 。
1
2
3
4
5
6
7

提示：

• 1 <= nums.length, k <= 10^5
• 1 <= nums[i] <= 10^9

class Solution {
    public long maxKelements(int[] nums, int k) {

    }
}
1
2
3
4
5

分析与题解

---

• 暴力求解 时间超时, 失败

  直接暴力法就是我们按照题意进行模拟运行, 每一次取完数组中的最后一个值就根据题意更新这个值, 然后重新排序整个数组.

  long result = 0;
  for(int i = 0; i < k; i++) {
      int num = nums[nums.length - 1];
      result += num;
      num = num/3 + (num%3 > 0 ? 1 : 0);
      nums[nums.length - 1] = num;
      Arrays.sort(nums);
  }
  1
  2
  3
  4
  5
  6
  7
  8

  整体的解题思路如下所示.

  class Solution {
      public long maxKelements(int[] nums, int k) {
          Arrays.sort(nums);
          long result = 0;
          for(int i = 0; i < k; i++) {
              int num = nums[nums.length - 1];
              result += num;
              num = num/3 + (num%3 > 0 ? 1 : 0);
              nums[nums.length - 1] = num;
              Arrays.sort(nums);
          }
          return result;
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14

  
  

  复杂度分析:

  • 时间复杂度: O(klogn), 时间复杂度与k相关, 排序需要损耗的时间复杂度为 logn
  • 空间复杂度: O(klogn), 需要 k 次排序, 每一次都要消耗的空间复杂度为 logn

  结果如下所示.

  

• 额外数组法

  既然暴力排序的方式时间超时, 其原因就在于Arrays.sort(nums);, 那我们就找一个不用排序的方式.

  我们发现, 当我们对 nums 排序完成之后, 然后取出最后一位数据时, 并进行 ceil(nums[i] / 3), 生成许多的 item, 一定有这样的规律: 先生成的 item 一定不小于后生成的 item 的值.

  比如 [1, 10, 3, 3, 3] 第一次是 ceil(10 / 3) = 4, 第二次是 ceil(4 / 3) = 2, 第三次是 ceil(3 / 3) = 1, 结果是 4 > 2 > 1, 结论是成立的.

  我们把这些 ceil(nums[i] / 3) 生成的 item 单独并且依次放在一个数组removeNums中, 那么这个数组removeNums也是有序的.

  由于 nums 不再删除数据了, 所以我们要用一个 index 记录当前 nums 中能取到的最大值.

  这时候取值过程就要分不同的逻辑分支了.

  • 当 removeNums 没有数据时, 我们就从 nums 中取最大值. 同时, index也需要偏移. 并且把 ceil(nums[i] / 3) 添加到 removeNums 中.

    

    int num = nums[numsIndex];
    result += num;
    removeNums.add(num/3 + (num%3 > 0 ? 1 : 0));
    numsIndex--;
    1
    2
    3
    4

  • 当 removeNums 有数据时, 我们就从 nums 中取最大值 和 从 removeNums 中取最大值, 两者取较大值. 当然了这时候还是需要更新 removeNums 的数据(删除最大值, 计算后放入数组尾部).

    

    int num = removeNums.get(0);
    removeNums.remove(0);
    result += num;
    removeNums.add(num/3 + (num%3 > 0 ? 1 : 0));
    1
    2
    3
    4

  接下来, 我们就一起看一下按照这个思路的整体的解题过程.

  class Solution {
      public long maxKelements(int[] nums, int k) {
          Arrays.sort(nums);
          long result = 0;
          ArrayList removeNums = new ArrayList<>();
          int numsIndex = nums.length - 1;
          for(int i = 0; i < k; i++) {
              // 条件1: 如果 numsIndex 小于等于0
              // 条件2: 如果当前removeNums有数据, 并且当前的removeNums的数据大于nums[numsIndex], 那就从removeNums中取出数据
              // numsIndex 下标大于等于0是边界条件
              if( numsIndex < 0 || (removeNums.size() != 0 && removeNums.get(0) > nums[numsIndex])) {
                  int num = removeNums.get(0);
                  removeNums.remove(0);
                  result += num;
                  removeNums.add(num/3 + (num%3 > 0 ? 1 : 0));
              } else {
                  int num = nums[numsIndex];
                  result += num;
                  removeNums.add(num/3 + (num%3 > 0 ? 1 : 0));
                  numsIndex--;
              }
          }
          return result;
      }
  }
  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

  
  

  复杂度分析:

  • 时间复杂度: O(k + logn), 遍历时间复杂度与k相关, 排序需要损耗的时间复杂度为 logn
  • 空间复杂度: O(logn), 排序消耗的空间复杂度为 logn

  结果如下所示.

  

• 优先队列法

  直接使用Java内置的优先队列 PriorityQueue, 这种方式我们不需要管理内部的排序逻辑, 直接通过 PriorityQueue来完成.

  首先就是把所有的数据添加到优先队列中.

  PriorityQueue q = new PriorityQueue((a, b) -> b - a);
  for (int num : nums) {
      q.offer(num);
  }
  1
  2
  3
  4

  然后就是通过 poll() 取出最大值, 然后计算后再添加到优先队列中.

  long ans = 0;
  for (int i = 0; i < k; ++i) {
      int num = q.poll();
      ans += num;
      q.offer(num/3 + (num%3 > 0 ? 1 : 0));
  }
  1
  2
  3
  4
  5
  6

  接下来, 我们一起看一下整体的代码逻辑.

  class Solution {
      public long maxKelements(int[] nums, int k) {
          PriorityQueue q = new PriorityQueue((a, b) -> b - a);
          for (int num : nums) {
              q.offer(num);
          }
          long ans = 0;
          for (int i = 0; i < k; ++i) {
              int num = q.poll();
              ans += num;
              q.offer(num/3 + (num%3 > 0 ? 1 : 0));
          }
          return ans;
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15

  复杂度分析:

  • 时间复杂度: O(nk), 遍历时间复杂度与k nums的长度 相关
  • 空间复杂度: O(n), 优先队列消耗的空间复杂度为 O(n)

  结果如下所示.