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]