3355. Zero Array Transformation I
思路:
用difference 矩阵
difference矩阵在你要对矩阵的1个区域加上相同的值很好用
假设要对[L,R]间的数加上5，那就将difference[L]+5、difference[R+1]-5
将difference矩阵进行prefix sum就可以得到进行相加后的矩阵了
e.g. 假设有一个 [1,3,4,6,10]他的difference矩阵就是[1,2,1,2,4]
要对[1,3]间的数加上4，就会变成[1,6,1,2,0]
最后对difference矩阵进行prefix sum 会变成 [1,7,8,10,10]
可以看出就是原本矩阵[1,3]区间加上4
这题其实就是要对一个长度n且元素都为0的矩阵 : array
按照queries相对应的区间依序加上1
最后看array[i]>=nums[i] 所有i都成立就可以达到题目要求
golang code :
func isZeroArray(nums []int, queries [][]int) bool {
diff := make([]int, len(nums)+1)
for _, val := range queries {
diff[val[0]]++
diff[val[1]+1]