题目描述
给你一个下标从 0 开始、长度为 n
的整数数组 nums
,和一个整数 k
。
你可以执行下述 递增 运算 任意 次(可以是 0
次):
- 从范围
[0, n - 1]
中选则一个下标i
,并将nums[i]
的值加1
。
如果数组中任何长度 大于或等于 3 的子数组,其 最大 元素都大于或等于 k
,则认为数组是一个 美丽数组。
以整数形式返回使数组变为 美丽数组 需要执行的 最小 递增运算数。
子数组是数组中的一个连续 非空 元素序列。
样例
输入: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。
输入: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。
输入: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
算法
(动态规划) $O(n)$
- 仅需要考虑长度为 $3$ 的所有子数组。
- 设状态 $f(i, 0)$ 表示前 $i$ 个元素都满足条件,且 $i$ 的值被修改为大于等于 $k$ 时,最少得增量运算次数。$f(i, 1)$ 是 $i-1$ 的值被修改为大于等于 $k$ 时,最少得增量运算次数。$f(i, 2)$ 是 $i-2$ 的值被修改为大于等于 $k$ 时,最少得增量运算次数。
- 初始时,$f(2, 0) = \max(0, k - nums(2))$,$f(2, 1)$ = \max(0, k - nums(1))$,$f(2, 2) = \max(0, k - nums(0))$。其余待定。
- 转移时,$f(i, 0) = \min(f(i - 1, 0), f(i - 1, 1), f(i - 1, 2)) + \max(0, k - nums(i))$,表示当前位置被修改大于等于 $k$ 时的增量运算,可以从上一个位置三种情况转移。$f(i, 1) = f(i - 1, 0)$,$f(i, 2) = f(i - 1, 1)$。后两种情况表示复用了上一个位置的大于等于 $k$ 的值。
- 最终答案为 $\min(f(n - 1, 0), f(n - 1, 1), f(n - 1, 2))$。
- 注意到每个位置的状态仅与上一个位置有关,故可以使用变量表示状态优化空间。
时间复杂度
- 状态数为 $O(n)$,转移时间为常数,故时间复杂度为 $O(n)$。
空间复杂度
- 优化后仅需要常数的额外空间。
C++ 代码
#define LL long long
class Solution {
public:
LL minIncrementOperations(vector<int>& nums, int k) {
const int n = nums.size();
LL f0 = max(0, k - nums[2]);
LL f1 = max(0, k - nums[1]);
LL f2 = max(0, k - nums[0]);
for (int i = 3; i < n; i++) {
LL t0 = min(f0, min(f1, f2)) + max(0, k - nums[i]);
LL t1 = f0;
LL t2 = f1;
f0 = t0; f1 = t1; f2 = t2;
}
return min(f0, min(f1, f2));
}
};