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

难度: Medium

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

Submission

运行时间: 62 ms

内存: 28.8 MB

class Solution:
    def checkArray(self, nums: List[int], k: int) -> bool:
        n=len(nums)
        dis=[0]*(n+1)
        sumD=0
        for i,x in enumerate(nums):
            sumD+=dis[i]#先来累加差分值，看前面对区间的操作对当前元素影响的总和
            x+=sumD#更新当前元素实际值
            if x==0:#如果==0，此时元素不用操作
                continue
            if x<0 or i+k>n:#如果小于0了或者已不能形成一个区间了，此时只能返回False，因为已经无力回天了
                return False
            sumD-=x#到达这说明此元素还可以操作，减去看对区间内的影响
            dis[i+k]+=x#超过此区间的不受影响
        return True

Explain

题解的思路基于差分数组的概念。差分数组允许我们对数组的子区间进行增减操作。在本题中，我们的目标是通过减少操作使得数组中的所有元素变为0。首先创建一个差分数组dis，初始全为0。遍历原数组，利用差分数组来更新当前元素实际值，并判断当前元素是否需要进一步操作。如果当前元素值已经为0，则不需要操作；如果当前元素值小于0或者无法形成长度为k的子区间，则返回false。否则，根据当前元素值调整差分数组，以反映对后续元素的影响。最终，如果能够遍历完整个数组而不返回false，则说明可以通过操作使所有元素变为0。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def checkArray(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        dis = [0] * (n + 1)  # 创建差分数组
        sumD = 0  # 累计差分值，用于调整nums中的实际值
        for i, x in enumerate(nums):
            sumD += dis[i]  # 更新当前元素值
            x += sumD
            if x == 0:  # 如果当前元素已经为0，无需操作
                continue
            if x < 0 or i + k > n:  # 如果元素小于0或无法形成完整子数组
                return False
            sumD -= x  # 减小当前元素值，反映到差分数组上
            dis[i + k] += x  # 调整差分数组，影响后续元素
        return True

Explore

使用差分数组的主要原因是它允许我们高效地进行区间修改。在处理需要频繁对数组的子区间增减的问题时，直接修改原数组会导致重复计算和较高的时间复杂度，尤其是在大数组和多次修改的情况下。差分数组通过记录每个区间的变化量，使得更新操作的时间复杂度从O(n)降低到O(1)，整体上提高了算法的效率。

在本题解中，确保不越界的关键在于算法逻辑中的条件检查`if i + k > n`。这个条件保证了在执行`dis[i + k] += x`操作时，索引`i + k`总是有效的，即不会超过数组`dis`的最大索引。这是因为数组`dis`的长度被定义为`n + 1`，因此即使在最大的有效索引`i + k`上进行操作，也不会越界。

在本题的逻辑中，如果在任何时刻元素`x`的值小于0，则意味着无法通过减少操作使其达到0，因为差分数组只能用于执行增减操作而不能改变操作的方向（只能做减法不能变为做加法）。因此，如果`x`已经小于0，则没有后续操作能将其增加到0，这导致无法满足题目要求使所有元素等于0，所以直接返回false是合理的。

在本题的框架和定义下，不存在这样的操作。差分数组的设计是基于增减相同的值于连续子区间，且这里的操作被设定为只能减少。如果元素值已经是负数，我们没有办法通过差分数组的减少操作来增加它的值。此外，题述中也没有提供其他机制或操作来允许从负数调整到0，因此在当前元素值小于0时返回false是符合题目逻辑的。