Question

2919. Minimum Increment Operations to Make Array Beautiful

中文文档

Description

You are given a 0-indexed integer array nums having length n, and an integer k.

You can perform the following increment operation any number of times (including zero):

• Choose an index i in the range [0, n - 1], and increase nums[i] by 1.

An array is considered beautiful if, for any subarray with a size of 3 or more, its maximum element is greater than or equal to k.

Return _an integer denoting the minimum number of increment operations needed to make _nums_ beautiful._

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [2,3,0,0,2], k = 4
Output: 3
Explanation: We can perform the following increment operations to make nums beautiful:
Choose index i = 1 and increase nums[1] by 1 -> [2,4,0,0,2].
Choose index i = 4 and increase nums[4] by 1 -> [2,4,0,0,3].
Choose index i = 4 and increase nums[4] by 1 -> [2,4,0,0,4].
The subarrays with a size of 3 or more are: [2,4,0], [4,0,0], [0,0,4], [2,4,0,0], [4,0,0,4], [2,4,0,0,4].
In all the subarrays, the maximum element is equal to k = 4, so nums is now beautiful.
It can be shown that nums cannot be made beautiful with fewer than 3 increment operations.
Hence, the answer is 3.

Example 2:

Input: nums = [0,1,3,3], k = 5
Output: 2
Explanation: We can perform the following increment operations to make nums beautiful:
Choose index i = 2 and increase nums[2] by 1 -> [0,1,4,3].
Choose index i = 2 and increase nums[2] by 1 -> [0,1,5,3].
The subarrays with a size of 3 or more are: [0,1,5], [1,5,3], [0,1,5,3].
In all the subarrays, the maximum element is equal to k = 5, so nums is now beautiful.
It can be shown that nums cannot be made beautiful with fewer than 2 increment operations.
Hence, the answer is 2.

Example 3:

Input: nums = [1,1,2], k = 1
Output: 0
Explanation: The only subarray with a size of 3 or more in this example is [1,1,2].
The maximum element, 2, is already greater than k = 1, so we don't need any increment operation.
Hence, the answer is 0.

 

Constraints:

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

Solutions

Solution 1: Dynamic Programming

We define $f$, $g$, and $h$ as the minimum number of increment operations needed to get the maximum value from the last three items in the first $i$ items, initially $f = 0$, $g = 0$, $h = 0$.

Next, we traverse the array $nums$. For each $x$, we need to update the values of $f$, $g$, and $h$ to meet the requirements of the problem, that is:

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

Finally, we only need to return the minimum value among $f$, $g$, and $h$.

The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $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);
  }
}