Readme

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差分即可恢复每个位置上的数值。