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

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

给你一个下标从 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 <= 10⁵
0 <= nums[i] <= 10⁹
0 <= k <= 10⁹

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: long long minIncrementOperations(vector<int>& nums, int k) { } };

golang 解法, 执行用时: 76 ms, 内存消耗: 8.7 MB, 提交时间: 2023-10-30 07:44:39

// 递推
func minIncrementOperations(nums []int, k int) int64 {
	var f0, f1, f2 int
	for _, x := range nums {
		inc := f0 + max(k-x, 0)
		f0 = min(inc, f1)
		f1 = min(inc, f2)
		f2 = inc
	}
	return int64(f0)
}

// 记忆化
func minIncrementOperations2(nums []int, k int) int64 {
	n := len(nums)
	memo := make([][3]int, n)
	for i := range memo {
		memo[i] = [3]int{-1, -1, -1}
	}
	var dfs func(int, int) int
	dfs = func(i, j int)  int {
		if i < 0 {
			return 0
		}
		p := &memo[i][j]
		if *p != -1 {
			return *p
		}
		res := dfs(i-1, 0) + max(k-nums[i], 0) // nums[i] 增大
		if j < 2 {
			res = min(res, dfs(i-1, j+1)) // nums[i] 不增大
		}
		*p = res
		return res
	}
	return int64(dfs(n-1, 0))
}

func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }

java 解法, 执行用时: 3 ms, 内存消耗: 58.9 MB, 提交时间: 2023-10-30 07:43:51

class Solution {
    public long minIncrementOperations(int[] nums, int k) {
        long f0 = 0, f1 = 0, f2 = 0;
        for (int x : nums) {
            long inc = f0 + Math.max(k - x, 0);
            f0 = Math.min(inc, f1);
            f1 = Math.min(inc, f2);
            f2 = inc;
        }
        return f0;
    }
}

java 解法, 执行用时: 49 ms, 内存消耗: 78.6 MB, 提交时间: 2023-10-30 07:43:39

class Solution {
    public long minIncrementOperations(int[] nums, int k) {
        int n = nums.length;
        long[][] memo = new long[n][3];
        for (long[] m : memo) {
            Arrays.fill(m, -1); // -1 表示没有计算过
        }
        return dfs(n - 1, 0, memo, nums, k);
    }
     
    private long dfs(int i, int j, long[][] memo, int[] nums, int k) {
        if (i < 0) { // 递归边界
            return 0;
        }
        if (memo[i][j] != -1) { // 之前计算过
            return memo[i][j];
        }
        long res = dfs(i - 1, 0, memo, nums, k) + Math.max(k - nums[i], 0); // nums[i] 增大
        if (j < 2) res = Math.min(res, dfs(i - 1, j + 1, memo, nums, k)); // nums[i] 不增大
        return memo[i][j] = res; // 记忆化
    }
}

cpp 解法, 执行用时: 296 ms, 内存消耗: 163.6 MB, 提交时间: 2023-10-30 07:43:24

class Solution {
public:
    long long minIncrementOperations1(vector<int>& nums, int k) {
        long long f0 = 0, f1 = 0, f2 = 0;
        for (int x : nums) {
            long long inc = f0 + max(k - x, 0);
            f0 = min(inc, f1);
            f1 = min(inc, f2);
            f2 = inc;
        }
        return f0;
    }

    long long minIncrementOperations(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<long long>> memo(n, vector<long long>(3, -1)); // -1 表示没有计算过
        function<long long(int, int)> dfs = [&](int i, int j) -> long long {
            if (i < 0) {
                return 0;
            }
            auto &res = memo[i][j]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }
            res = dfs(i - 1, 0) + max(k - nums[i], 0); // nums[i] 增大
            if (j < 2) res = min(res, dfs(i - 1, j + 1)); // nums[i] 不增大
            return res;
        };
        return dfs(n - 1, 0);
    }
};

python3 解法, 执行用时: 220 ms, 内存消耗: 30.6 MB, 提交时间: 2023-10-30 07:43:00

class Solution:
    def minIncrementOperations1(self, nums: List[int], k: int) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i < 0:
                return 0
            res = dfs(i - 1, 0) + max(k - nums[i], 0)  # nums[i] 增大
            if j < 2:
                res = min(res, dfs(i - 1, j + 1))  # nums[i] 不增大
            return res
        return dfs(len(nums) - 1, 0)
        
    # 递推
    def minIncrementOperations(self, nums: List[int], k: int) -> int:
        f0 = f1 = f2 = 0
        for x in nums:
            inc = f0 + max(k - x, 0)
            f0 = min(inc, f1)
            f1 = min(inc, f2)
            f2 = inc
        return f0

上一题

下一题

详情