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

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

/*
题目思路：
使用 Java Stream API 可以更简洁地解决这个问题。通过使用 map 操作，将小于 k 的元素增加到 k，同时计算增加的次数。
*/

import java.util.Arrays;

public class Solution {
    public int minIncrements(int[] nums, int k) {
        return Arrays.stream(nums)
                     .map(num -> num < k ? k - num : 0)
                     .sum();
    }
}

这道题的解法使用了动态规划的思想。设f[i]表示使得以索引i结尾的，长度至少为3的所有子数组的最大值都至少为k的最小增量操作数。初始时，f[0]、f[1]、f[2]分别计算nums数组前三个元素与k的差值，若已经大于或等于k则为0。对于每一个后续的元素x，计算使得x大于等于k所需的增量t。然后更新f[2]为t加上前三个f中的最小值（这确保任意长度大于等于3的子数组的最大值都大于等于k），并将f[0]、f[1]向前推进一位。最终，最小的f值即为所求答案，因为它表示的是数组最后三个元素满足条件的最小操作数。

O(n)

O(1)