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

动态规划解题：最小操作次数使数组变为美丽数组

问题描述

给定一个下标从0开始、长度为n的整数数组nums和一个整数k。你可以对数组中的任意一个元素进行加1操作，操作次数不限。如果数组中任意长度大于或等于3的子数组的最大值都大于或等于k，则称该数组为美丽数组。我们需要找到使数组变为美丽数组所需的最小操作次数。

问题分析

这个问题的核心是如何通过最少的操作次数，使得数组满足特定的条件。具体来说，我们需要确保数组中所有长度大于或等于3的子数组的最大值都大于或等于k。为了实现这一目标，我们可以使用动态规划的方法。

动态规划思路

动态规划是一种将复杂问题分解为子问题的算法思想。在这个问题中，我们可以定义一个数组dp[i]，表示将数组nums的前i个元素变成美丽数组所需的最小操作次数。

状态定义

• dp[i]：表示将数组nums的前i个元素变成美丽数组所需的最小操作次数。

状态转移

对于每个位置i，我们需要考虑以下三种情况：

1. 只考虑当前元素：即nums[i]单独作为一个子数组的一部分。

2. 当前元素与前一个元素一起考虑：即nums[i]和nums[i-1]作为一个长度为2的子数组的一部分。

3. 当前元素与前两个元素一起考虑：即nums[i]、nums[i-1]和nums[i-2]作为一个长度为3的子数组。

为了满足美丽数组的条件，我们需要确保：

• 如果只考虑当前元素，那么nums[i]必须大于或等于k。

• 如果考虑当前元素与前一个元素，那么nums[i]和nums[i-1]中至少有一个必须大于或等于k。

• 如果考虑当前元素与前两个元素，那么nums[i]、nums[i-1]和nums[i-2]中至少有一个必须大于或等于k。

因此，dp[i]的值应该是：

• 如果nums[i] >= k，则dp[i] = min(dp[i-1], dp[i-2], dp[i-3])。

• 如果nums[i] < k，则dp[i] = min(dp[i-1], dp[i-2], dp[i-3]) + (k - nums[i])。

初始化

• 如果数组长度小于3，直接返回0，因为不存在长度大于或等于3的子数组。

• 初始化dp[0]、dp[1]和dp[2]：

  • dp[0] = Math.max(0, k - nums[0])：只考虑第一个元素nums[0]，如果它小于k，则需要k - nums[0]次操作。

  • dp[1] = Math.max(0, k - nums[1])：只考虑第二个元素nums[1]，如果它小于k，则需要k - nums[1]次操作。

  • dp[2] = Math.max(0, k - nums[2])：只考虑第三个元素nums[2]，如果它小于k，则需要k - nums[2]次操作。

返回结果

最终返回dp[n-1]、dp[n-2]和dp[n-3]中的最小值。这是因为最后一个元素可能与前两个元素一起考虑，因此需要选择最小的操作次数。

代码实现

以下是Java代码实现：

class Solution {public long minIncrementOperations(int[] nums, int k) {int n = nums.length;if (n < 3) {return 0; // 如果数组长度小于3，直接返回0}// dp[i]表示将数组nums的前i个元素变成美丽数组所需的最小操作次数long[] dp = new long[n];dp[0] = Math.max(0, k - nums[0]); // 初始化第一个位置dp[1] = Math.max(0, k - nums[1]); // 初始化第二个位置dp[2] = Math.max(0, k - nums[2]); // 初始化第三个位置// 动态规划计算for (int i = 3; i < n; i++) {// 当前位置需要的操作次数long currentCost = Math.max(0, k - nums[i]);// 选择最小的操作次数dp[i] = Math.min(dp[i - 1], Math.min(dp[i - 2], dp[i - 3])) + currentCost;}// 返回最后三个位置的最小值return Math.min(dp[n - 1], Math.min(dp[n - 2], dp[n - 3]));}
}

示例解析

假设nums = [2, 3, 5, 1, 4]，k = 4。

1. 初始化：

   • dp[0] = Math.max(0, 4 - 2) = 2

   • dp[1] = Math.max(0, 4 - 3) = 1

   • dp[2] = Math.max(0, 4 - 5) = 0

2. 动态规划计算：

   • i = 3：

     • currentCost = Math.max(0, 4 - 1) = 3

     • dp[3] = min(dp[2], dp[1], dp[0]) + currentCost = min(0, 1, 2) + 3 = 3

   • i = 4：

     • currentCost = Math.max(0, 4 - 4) = 0

     • dp[4] = min(dp[3], dp[2], dp[1]) + currentCost = min(3, 0, 1) + 0 = 0

3. 返回结果：

   • Math.min(dp[4], Math.min(dp[3], dp[2])) = Math.min(0, Math.min(3, 0)) = 0

因此，最终结果是0，表示不需要任何操作即可满足条件。

总结

通过动态规划，我们可以高效地解决这个问题。动态规划的关键在于：

1. 定义合适的状态dp[i]。

2. 找到状态转移方程。

3. 初始化边界条件。

4. 返回最终结果。

希望这篇博客能帮助你更好地理解这个问题的解法！如果你有任何疑问或需要进一步的解释，欢迎留言讨论。