Skip to content

Latest commit

 

History

History
204 lines (158 loc) · 5.86 KB

File metadata and controls

204 lines (158 loc) · 5.86 KB
comments difficulty edit_url rating source tags
true
中等
2030
第 369 场周赛 Q3
数组
动态规划

English Version

题目描述

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

解法

方法一:动态规划

我们定义 $f$, $g$, $h$ 表示前 $i$ 项中,分别以最后三项作为子数组的最大值所需要的最小增量运算数,初始时 $f = 0$, $g = 0$, $h = 0$

接下来,我们遍历数组 $nums$,对于每个 $x$,我们需要更新 $f$, $g$, $h$ 的值,使其满足题目要求,即:

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

最后,我们只需要返回 $f$, $g$, $h$ 中的最小值即可。

时间复杂度 $O(n)$,其中 $n$ 为数组长度。空间复杂度 $O(1)$

Python3

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)

Java

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);
    }
}

C++

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});
    }
};

Go

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))
}

TypeScript

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);
}

C#

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);
    }
}