Leetcode 3356. Zero Array Transformation II

• Leetcode 3356. Zero Array Transformation II
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3356. Zero Array Transformation II

1. 解题思路

这一题需要和题目3355结合起来一起看。

整体来说，这道题可以拆分为以下两个子命题：

• 给定任意一个query序列queries，判断其能否使得数组归0；
• 找到一个最小的$k$，使得query序列queries[:k]使得数组可以归零。

其中，对于第一个问题，其实和题目3355是完全等价的，我们只需要用一个累积数组来考察每一个数字最多可以有多大的改变量，然后考察改变量是否大于等于其原先的值即可判断其是否可以在query下归零。

而对于第二个问题，我们只需要使用一个二分查找即可解决。

2. 代码实现

给出python代码实现如下：

class Solution:
    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
        n, m = len(nums), len(queries)
        
        def is_possible(k):
            cnt = [0 for _ in range(n+1)]
            for l, r, val in queries[:k]:
                cnt[l] += val
                cnt[r+1] -= val
            cnt = list(accumulate(cnt))
            return all(cnt[i] >= nums[i] for i in range(n))
        
        if all(x == 0 for x in nums):
            return 0
        if not is_possible(m):
            return -1
        i, j = 0, m
        while j-i > 1:
            k = (i+j) // 2
            if is_possible(k):
                j = k
            else:
                i = k
        return j

提交代码评测得到：耗时686ms，占用内存57.2MB。