什么是差分?jǐn)?shù)組

差分?jǐn)?shù)組是一種數(shù)據(jù)結(jié)構(gòu)，它存儲(chǔ)的是一個(gè)數(shù)組每個(gè)相鄰元素的差值。換句話說(shuō)，給定一個(gè)數(shù)組arr[]，其對(duì)應(yīng)的差分?jǐn)?shù)組diff[]將滿足：

diff[i] = arr[i+1] - arr[i] 對(duì)于所有 0 <= i < n-1

差分?jǐn)?shù)組的作用

用于高效地實(shí)現(xiàn)某些特定的數(shù)組操作，如對(duì)某一范圍的數(shù)組元素全部增加或減少一個(gè)固定值。

例如，考慮一個(gè)簡(jiǎn)單的數(shù)組：

arr = [1, 2, 3, 4, 5]

其差分?jǐn)?shù)組為：

diff = [1, 1, 1, 1]

假設(shè)我們想將arr數(shù)組的索引[1, 3]范圍內(nèi)的所有元素都加上2。如果使用常規(guī)方法，我們需要遍歷這個(gè)子數(shù)組，并對(duì)每個(gè)元素加上2。但是如果我們使用差分?jǐn)?shù)組，只需要做兩步操作：

1. diff[1] += 2
2. diff[4] -= 2（注意這里的4是3的下一個(gè)索引，但由于diff的長(zhǎng)度比arr小1，所以它實(shí)際上是diff數(shù)組的最后一個(gè)元素）

然后，我們可以通過(guò)差分?jǐn)?shù)組重新構(gòu)建arr數(shù)組，只需要從第一個(gè)元素開(kāi)始，不斷地將差分值加回去。

算法中的應(yīng)用

leetcode 2770 數(shù)組的最大美麗值

假如通過(guò)查找所有可能的變動(dòng)區(qū)間并求其最大重疊次數(shù)，那么就可以采用差分?jǐn)?shù)組的思路

當(dāng)然這道題也有更簡(jiǎn)單的思路，比如把整個(gè)數(shù)組sort之后，問(wèn)題轉(zhuǎn)換為了"首尾元素差值不大于2K的最長(zhǎng)子數(shù)組長(zhǎng)度"