class Solution {
public:
bool checkArray(vector<int>& nums, int k) {
}
};
6919. 使数组中的所有元素都等于零
给你一个下标从 0 开始的整数数组 nums 和一个正整数 k 。
你可以对数组执行下述操作 任意次 ：
k 的 任一 子数组，并将子数组中每个元素都 减去 1 。如果你可以使数组中的所有元素都等于 0 ，返回 true ；否则，返回 false 。
子数组 是数组中的一个非空连续元素序列。
示例 1：
输入：nums = [2,2,3,1,1,0], k = 3 输出：true 解释：可以执行下述操作： - 选出子数组 [2,2,3] ，执行操作后，数组变为 nums = [1,1,2,1,1,0] 。 - 选出子数组 [2,1,1] ，执行操作后，数组变为 nums = [1,1,1,0,0,0] 。 - 选出子数组 [1,1,1] ，执行操作后，数组变为 nums = [0,0,0,0,0,0] 。
示例 2：
输入：nums = [1,3,1,1], k = 2 输出：false 解释：无法使数组中的所有元素等于 0 。
提示：
1 <= k <= nums.length <= 1050 <= nums[i] <= 106原站题解
javascript 解法, 执行用时: 104 ms, 内存消耗: 53.3 MB, 提交时间: 2023-07-10 10:09:09
/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var checkArray = function (nums, k) {
const n = nums.length;
let d = new Array(n + 1).fill(0);
let sumD = 0;
for (let i = 0; i < n; i++) {
sumD += d[i];
let x = nums[i];
x += sumD;
if (x == 0) continue; // 无需操作
if (x < 0 || i + k > n) return false; // 无法操作
sumD -= x; // 直接加到 sumD 中
d[i + k] += x;
}
return true;
};
golang 解法, 执行用时: 104 ms, 内存消耗: 9.2 MB, 提交时间: 2023-07-10 10:08:32
func checkArray(nums []int, k int) bool {
n := len(nums)
d := make([]int, n+1)
sumD := 0
for i, x := range nums {
sumD += d[i]
x += sumD
if x == 0 { // 无需操作
continue
}
if x < 0 || i+k > n { // 无法操作
return false
}
sumD -= x // 直接加到 sumD 中
d[i+k] += x
}
return true
}
cpp 解法, 执行用时: 116 ms, 内存消耗: 95.2 MB, 提交时间: 2023-07-10 10:08:19
class Solution {
public:
bool checkArray(vector<int> &nums, int k) {
int n = nums.size(), sum_d = 0;
vector<int> d(n + 1);
for (int i = 0; i < n; i++) {
sum_d += d[i];
int x = nums[i];
x += sum_d;
if (x == 0) continue; // 无需操作
if (x < 0 || i + k > n) return false; // 无法操作
sum_d -= x; // 直接加到 sum_d 中
d[i + k] += x;
}
return true;
}
};
java 解法, 执行用时: 2 ms, 内存消耗: 55.1 MB, 提交时间: 2023-07-10 10:08:06
class Solution {
public boolean checkArray(int[] nums, int k) {
int n = nums.length, sumD = 0;
var d = new int[n + 1];
for (int i = 0; i < n; i++) {
sumD += d[i];
int x = nums[i];
x += sumD;
if (x == 0) continue; // 无需操作
if (x < 0 || i + k > n) return false; // 无法操作
sumD -= x; // 直接加到 sumD 中
d[i + k] += x;
}
return true;
}
}
python3 解法, 执行用时: 132 ms, 内存消耗: 28.6 MB, 提交时间: 2023-07-10 10:07:45
'''
差分数组
'''
class Solution:
def checkArray(self, nums: List[int], k: int) -> bool:
n = len(nums)
d = [0] * (n + 1)
sum_d = 0
for i, x in enumerate(nums):
sum_d += d[i]
x += sum_d
if x == 0: continue # 无需操作
if x < 0 or i + k > n: return False # 无法操作
sum_d -= x # 直接加到 sum_d 中
d[i + k] += x
return True