今日题目

https://leetcode.com/problems/zero-array-transformation-i/

直觉

本题的意思是：对于每次查询，在区间 (l, r) 内将元素减一。 对于区间内的批量修改，可以考虑使用差分数组。 注意题目说的是"选取下标的一个子集"，也就是说我们不一定要对区间内所有下标都减一。 因此，由于我们只关心最终数组是否为零数组，结合题目中子集的含义，我们可以判断最终数组的每个元素是否小于等于零，而不是严格等于零。

思路

对于每次查询，在差分数组的 l 位置加 1，在 r + 1 位置减 1。 然后在计算最终结果时，对差分数组求前缀和，得到每个位置的总变化量。 最后，将差分数组的前缀和叠加到原数组上，判断每个位置的值是否小于等于零，即可得出答案。

复杂度

  • 时间复杂度：

$O(N + M)$，N 为原数组长度，M 为查询数组长度。

  • 空间复杂度：

$O(N)$。

代码

class Solution:
    def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
        diff = [0] * (len(nums) + 1)
        for l, r in queries:  
            diff[l] -= 1
            diff[r + 1] += 1
        
        for i in range(len(nums)):
            if i > 0:
                diff[i] += diff[i-1]
            if nums[i] + diff[i] > 0:
                # print(i, nums[i], diff[i])
                return False
        
        return True

image.png

更多解题思路，欢迎访问 我的博客