Question

2919. 使数组变美的最小增量运算数

English Version

题目描述

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和一个整数 k 。

你可以执行下述 递增 运算 任意 次（可以是 0 次）：

• 从范围 [0, n - 1] 中选择一个下标 i ，并将 nums[i] 的值加 1 。

如果数组中任何长度 大于或等于 3 的子数组，其 最大 元素都大于或等于 k ，则认为数组是一个 美丽数组 。

以整数形式返回使数组变为 美丽数组 需要执行的 最小 递增运算数。

子数组是数组中的一个连续 非空 元素序列。

 

示例 1：

输入：nums = [2,3,0,0,2], k = 4
输出：3
解释：可以执行下述递增运算，使 nums 变为美丽数组：
选择下标 i = 1 ，并且将 nums[1] 的值加 1 -> [2,4,0,0,2] 。
选择下标 i = 4 ，并且将 nums[4] 的值加 1 -> [2,4,0,0,3] 。
选择下标 i = 4 ，并且将 nums[4] 的值加 1 -> [2,4,0,0,4] 。
长度大于或等于 3 的子数组为 [2,4,0], [4,0,0], [0,0,4], [2,4,0,0], [4,0,0,4], [2,4,0,0,4] 。
在所有子数组中，最大元素都等于 k = 4 ，所以 nums 现在是美丽数组。
可以证明无法用少于 3 次递增运算使 nums 变为美丽数组。
因此，答案为 3 。

示例 2：

输入：nums = [0,1,3,3], k = 5
输出：2
解释：可以执行下述递增运算，使 nums 变为美丽数组：
选择下标 i = 2 ，并且将 nums[2] 的值加 1 -> [0,1,4,3] 。
选择下标 i = 2 ，并且将 nums[2] 的值加 1 -> [0,1,5,3] 。
长度大于或等于 3 的子数组为 [0,1,5]、[1,5,3]、[0,1,5,3] 。
在所有子数组中，最大元素都等于 k = 5 ，所以 nums 现在是美丽数组。
可以证明无法用少于 2 次递增运算使 nums 变为美丽数组。 
因此，答案为 2 。

示例 3：

输入：nums = [1,1,2], k = 1
输出：0
解释：在这个示例中，只有一个长度大于或等于 3 的子数组 [1,1,2] 。
其最大元素 2 已经大于 k = 1 ，所以无需执行任何增量运算。
因此，答案为 0 。

 

提示：

• 3 <= n == nums.length <= 105
• 0 <= nums[i] <= 109
• 0 <= k <= 109

解法

方法一：动态规划

我们定义 $f$, $g$, $h$ 表示前 $i$ 项中，分别以最后三项作为子数组的最大值所需要的最小增量运算数，初始时 $f = 0$, $g = 0$, $h = 0$。

接下来，我们遍历数组 $nums$，对于每个 $x$，我们需要更新 $f$, $g$, $h$ 的值，使其满足题目要求，即：

$$ \begin{aligned} f' &= g \ g' &= h \ h' &= \min(f, g, h) + \max(k - x, 0) \end{aligned} $$

最后，我们只需要返回 $f$, $g$, $h$ 中的最小值即可。

时间复杂度 $O(n)$，其中 $n$ 为数组长度。空间复杂度 $O(1)$。

class Solution:
  def minIncrementOperations(self, nums: List[int], k: int) -> int:
    f = g = h = 0
    for x in nums:
      f, g, h = g, h, min(f, g, h) + max(k - x, 0)
    return min(f, g, h)

class Solution {
  public long minIncrementOperations(int[] nums, int k) {
    long f = 0, g = 0, h = 0;
    for (int x : nums) {
      long hh = Math.min(Math.min(f, g), h) + Math.max(k - x, 0);
      f = g;
      g = h;
      h = hh;
    }
    return Math.min(Math.min(f, g), h);
  }
}

class Solution {
public:
  long long minIncrementOperations(vector<int>& nums, int k) {
    long long f = 0, g = 0, h = 0;
    for (int x : nums) {
      long long hh = min({f, g, h}) + max(k - x, 0);
      f = g;
      g = h;
      h = hh;
    }
    return min({f, g, h});
  }
};

func minIncrementOperations(nums []int, k int) int64 {
  var f, g, h int
  for _, x := range nums {
    f, g, h = g, h, min(f, g, h)+max(k-x, 0)
  }
  return int64(min(f, g, h))
}

function minIncrementOperations(nums: number[], k: number): number {
  let [f, g, h] = [0, 0, 0];
  for (const x of nums) {
    [f, g, h] = [g, h, Math.min(f, g, h) + Math.max(k - x, 0)];
  }
  return Math.min(f, g, h);
}

public class Solution {
  public long MinIncrementOperations(int[] nums, int k) {
    long f = 0, g = 0, h = 0;
    foreach (int x in nums) {
      long hh = Math.Min(Math.Min(f, g), h) + Math.Max(k - x, 0);
      f = g;
      g = h;
      h = hh;
    }
    return Math.Min(Math.Min(f, g), h);
  }
}