2772-使数组中的所有元素都等于零

给你一个下标从 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 <= 105
• 0 <= nums[i] <= 106

下午两点【b站@灵茶山艾府】 直播讲题，欢迎关注！

提示 1

想一想，如果 nums}[0]>0，那么必须要执行什么样的操作？

提示 2

对于 nums}[0]>0 的情况，必须把 nums}[0] 到 nums}[k-1] 都减去 nums}[0]。

然后思考 nums}[1] 要怎么处理，依此类推。

提示 3

子数组同时加上/减去一个数，非常适合用差分数组来维护。

设差分数组为 d。那么把 nums}[i] 到 nums}[i+k-1] 同时减去 1，等价于把 d[i] 减 1，d[i+k] 加 1。

注意子数组长度必须恰好等于 k，所以当 i+k\le n 时，才能执行上述操作。

遍历数组的同时，用变量 sumD 累加差分值。遍历到 nums}[i] 时，nums}[i]+\textit{sumD 就是 nums}[i] 的实际值了。

分类讨论：

• 如果 nums}[i]<0，由于无法让元素值增大，返回 false。
• 如果 nums}[i]=0，无需操作，遍历下一个数。
• 如果 nums}[i]>0：
  • 如果 i+k> n，无法执行操作，所以 nums}[i] 无法变成 0，返回 false。
  • 如果 i+k\le n，按照上面说的执行操作，修改差分数组，遍历下一个数。

如果遍历中途没有返回 false，那么最后返回 true。

[sol-Python3]

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

[sol-Java]

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

[sol-C++]

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

[sol-Go]

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
}

[sol-JavaScript]

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

复杂度分析

• 时间复杂度：\mathcal{O}(n)，其中 n 为 nums 的长度。
• 空间复杂度：\mathcal{O}(n)。

相似题目

• 2528. 最大化城市的最小供电站数目