Medium

题目描述

给你一个长度为 n 的下标从 0 开始的整数数组 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 <= 10^5
  • 0 <= nums[i] <= 10^9
  • 0 <= k <= 10^9

解题思路

这道题的关键是理解题意：数组美丽意味着每个长度≥3的子数组都有至少一个元素≥k。

核心观察： 如果我们把数组从左到右分成连续的长度为3的窗口，那么每个窗口内都必须有至少一个元素≥k。这样就能保证所有长度≥3的子数组都满足条件。

动态规划思路：

  • 定义 dp[i] 为使前i+1个元素满足美丽条件，且第i个位置的元素≥k的最小操作数
  • 状态转移：dp[i] = max(0, k - nums[i]) + min(dp[i-1], dp[i-2], dp[i-3])
    • max(0, k - nums[i])：把第i个位置增加到k所需的操作数
    • min(dp[i-1], dp[i-2], dp[i-3])：前面3个位置中选择代价最小的作为"保证位置"

初始状态： 前三个位置分别作为保证位置的代价

最终答案： 最后三个位置中的最小值，因为最后一个窗口可以选择任意位置作为保证位置

这种方法保证了每个连续的3个元素中都有一个≥k，从而满足所有子数组的要求。

代码实现

class Solution {
public:
    long long minIncrementOperations(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> dp(n);
        
        // 初始化前三个位置
        for (int i = 0; i < 3; i++) {
            dp[i] = max(0, k - nums[i]);
        }
        
        // 动态规划转移
        for (int i = 3; i < n; i++) {
            long long cost = max(0, k - nums[i]);
            dp[i] = cost + min({dp[i-1], dp[i-2], dp[i-3]});
        }
        
        // 返回最后三个位置的最小值
        return min({dp[n-1], dp[n-2], dp[n-3]});
    }
};

class Solution:
    def minIncrementOperations(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [0] * n
        
        # 初始化前三个位置
        for i in range(3):
            dp[i] = max(0, k - nums[i])
        
        # 动态规划转移
        for i in range(3, n):
            cost = max(0, k - nums[i])
            dp[i] = cost + min(dp[i-1], dp[i-2], dp[i-3])
        
        # 返回最后三个位置的最小值
        return min(dp[n-1], dp[n-2], dp[n-3])

public class Solution {
    public long MinIncrementOperations(int[] nums, int k) {
        int n = nums.Length;
        long[] dp = new long[n];
        
        // 初始化前三个位置
        for (int i = 0; i < 3; i++) {
            dp[i] = Math.Max(0, k - nums[i]);
        }
        
        // 动态规划转移
        for (int i = 3; i < n; i++) {
            long cost = Math.Max(0, k - nums[i]);
            dp[i] = cost + Math.Min(dp[i-1], Math.Min(dp[i-2], dp[i-3]));
        }
        
        // 返回最后三个位置的最小值
        return Math.Min(dp[n-1], Math.Min(dp[n-2], dp[n-3]));
    }
}

var minIncrementOperations = function(nums, k) {
    const n = nums.length;
    const dp = new Array(n);
    
    // 初始化前三个位置
    for (let i = 0; i < 3; i++) {
        dp[i] = Math.max(0, k - nums[i]);
    }
    
    // 动态规划转移
    for (let i = 3; i < n; i++) {
        const cost = Math.max(0, k - nums[i]);
        dp[i] = cost + Math.min(dp[i-1], dp[i-2], dp[i-3]);
    }
    
    // 返回最后三个位置的最小值
    return Math.min(dp[n-1], dp[n-2], dp[n-3]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

注：可以进一步优化空间复杂度到O(1)，只保存最近的三个dp值即可。