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

标签: 数组 动态规划

难度: Medium

给你一个下标从 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

Submission

运行时间: 145 ms

内存: 30.0 MB

class Solution:
    def minIncrementOperations(self, nums: List[int], k: int) -> int:
        n = len(nums)
        f0 = k - nums[0] if nums[0] < k else 0
        f1 = k - nums[1] if nums[1] < k else 0
        f2 = k - nums[2] if nums[2] < k else 0
        for x in nums[3:]:
            t = k - x if x < k else 0
            f0, f1, f2 = f1, f2, t + min(f0,f1,f2)
        return min(f0, f1, f2)

Explain

这道题的解法使用了动态规划的思想。设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)

# 定义一个类Solution
class Solution:
    def minIncrementOperations(self, nums: List[int], k: int) -> int:
        n = len(nums)  # 数组的长度
        # 初始化f0, f1, f2
        f0 = k - nums[0] if nums[0] < k else 0
        f1 = k - nums[1] if nums[1] < k else 0
        f2 = k - nums[2] if nums[2] < k else 0
        # 遍历数组从第4个元素开始
        for x in nums[3:]:
            t = k - x if x < k else 0  # 计算当前元素x达到k所需的增量
            # 更新状态，保证任何长度>=3的子数组的最大值都>=k
            f0, f1, f2 = f1, f2, t + min(f0, f1, f2)
        # 返回最小的操作数，确保整个数组变为美数组
        return min(f0, f1, f2)

Explore

在这个动态规划解法中，f[i]表示的是使得以索引i结尾的、长度至少为3的所有子数组的最大值都至少为k的最小增量操作数。这一值是通过结合当前元素到达k需要的增量与前三个元素中存储的最小操作数来更新的，确保任意长度大于等于3的子数组的最大值都至少为k。这样，通过持续更新这三个状态，可以确保每一次迭代后，f[i]都能正确地反映出以当前元素结尾的、满足条件的子数组的最小操作数。

因为题目要求的是长度至少为3的子数组，所以在更新每个f[i]时，只需考虑以当前元素为结尾且长度至少为3的子数组。这样的设计通过每次只保留最近三个f值，并将当前元素与这三个值结合更新，保证了任何长度大于等于3的子数组的最大值都能满足条件。这三个值足以覆盖所有长度大于等于3的子数组的情况，因为任何更长的子数组的最小操作数也会在这三个值中反映。

如果数组长度小于3，那么不存在长度至少为3的子数组，因此按照题目的要求，没有必要执行任何操作。在这种情况下，可以在动态规划算法的开始部分加入一个检查，如果数组长度小于3，则直接返回0，因为不需要任何增量操作。

使用min函数选择最小值的原因是，我们希望最小化整个数组满足条件的总增量操作数。通过选择前三个f值中的最小值并结合当前元素所需的最小增量，可以保证以当前元素结尾的、长度至少为3的子数组在增量操作尽可能小的情况下满足最大值至少为k的条件。这种方法确保了我们总是选择最优的（即成本最低的）操作策略来更新动态规划的状态。