Back to Leetcode

Readme

Others/2772.Apply-Operations-to-Make-All-Array-Elements-Equal-to-Zero/Readme.md

latest1.3 KB
Original Source

2745.Construct-the-Longest-New-String

我们将问题反过来看,就是问是否能将一个长度为n的全0数组,通过若干次的“k-size subarray +1”操作变成nums。

显然,对于第一个元素,想实现0->nums[0],相差delta=nums[0]-0,我们必须通过将[0:k-1]整体增加delta来实现。

此时观察第二个元素,已经是nums[0]了。如果这个数值大于nums[1],显然我们无法通过任何只增不减的操作实现变换,故返回false。否则意味着我们还差delta=nums[1]-nums[0],必须需要将[1:k]整体提升delta

从上面的过程我们已经发现规律。从前往后遍历时,每个位置i可能已经有了某个数值(受之前操作的影响)。为了实现与预定目标nums[i]的匹配(假设相差delta),那必须进行操作将[i:i+k-1]整体提升delta。而这些操作会影响到后续位置的数值。我们通过当前值与预期的nums[i]的大小关系,可以判定是否无解。

最终,如果最后一个元素的当前值与nums[n-1]完全一致时,说明整套操作能够实现目标。

很明显,对于区间整体的增减,我们需要差分数组来标记。比如,我们要将[i:i+k-1]整体提升d,那么只需要标记diff[i]+=d, diff[i+k]-=d即可. 从零开始,一路前往后累积diff差分即可恢复每个位置上的数值。