基礎(chǔ)算法:差分?jǐn)?shù)組詳解

讀完本文，可以去力扣解決如下題目：

370. 區(qū)間加法（中等）

1109. 航班預(yù)訂統(tǒng)計(jì)（中等）

1094. 拼車（中等）

PS：這是一年前發(fā)布的論那些小而美的算法技巧：差分?jǐn)?shù)組/前綴和，我優(yōu)化并添加了很多內(nèi)容，重新發(fā)一遍。

前文說(shuō)前綴和主要適用的場(chǎng)景是原始數(shù)組不會(huì)被修改的情況下，頻繁查詢某個(gè)區(qū)間的累加和。

這里簡(jiǎn)單介紹一下前綴和，核心代碼就是下面這段：

classPrefixSum{
//前綴和數(shù)組
privateint[]prefix;

/*輸入一個(gè)數(shù)組，構(gòu)造前綴和*/
publicPrefixSum(int[]nums){
prefix=newint[nums.length+1];
//計(jì)算nums的累加和
for(inti=1;i1]+nums[i-1];
}
}

/*查詢閉區(qū)間[i,j]的累加和*/
publicintquery(inti,intj){
returnprefix[j+1]-prefix[i];
}
}

prefix[i]就代表著nums[0..i-1]所有元素的累加和，如果我們想求區(qū)間nums[i..j]的累加和，只要計(jì)算prefix[j+1] - prefix[i]即可，而不需要遍歷整個(gè)區(qū)間求和。

本文講一個(gè)和前綴和思想非常類似的算法技巧「差分?jǐn)?shù)組」，差分?jǐn)?shù)組的主要適用場(chǎng)景是頻繁對(duì)原始數(shù)組的某個(gè)區(qū)間的元素進(jìn)行增減。

比如說(shuō)，我給你輸入一個(gè)數(shù)組nums，然后又要求給區(qū)間nums[2..6]全部加 1，再給nums[3..9]全部減 3，再給nums[0..4]全部加 2，再給…

一通操作猛如虎，然后問(wèn)你，最后nums數(shù)組的值是什么？

常規(guī)的思路很容易，你讓我給區(qū)間nums[i..j]加上val，那我就一個(gè) for 循環(huán)給它們都加上唄，還能咋樣？這種思路的時(shí)間復(fù)雜度是 O(N)，由于這個(gè)場(chǎng)景下對(duì)nums的修改非常頻繁，所以效率會(huì)很低下。

這里就需要差分?jǐn)?shù)組的技巧，類似前綴和技巧構(gòu)造的prefix數(shù)組，我們先對(duì)nums數(shù)組構(gòu)造一個(gè)diff差分?jǐn)?shù)組，diff[i]就是nums[i]和nums[i-1]之差：

int[]diff=newint[nums.length];
//構(gòu)造差分?jǐn)?shù)組
diff[0]=nums[0];
for(inti=1;i1];
}

通過(guò)這個(gè)diff差分?jǐn)?shù)組是可以反推出原始數(shù)組nums的，代碼邏輯如下：

int[]res=newint[diff.length];
//根據(jù)差分?jǐn)?shù)組構(gòu)造結(jié)果數(shù)組
res[0]=diff[0];
for(inti=1;i1]+diff[i];
}

這樣構(gòu)造差分?jǐn)?shù)組diff，就可以快速進(jìn)行區(qū)間增減的操作，如果你想對(duì)區(qū)間nums[i..j]的元素全部加 3，那么只需要讓diff[i] += 3，然后再讓diff[j+1] -= 3即可：

原理很簡(jiǎn)單，回想diff數(shù)組反推nums數(shù)組的過(guò)程，diff[i] += 3意味著給nums[i..]所有的元素都加了 3，然后diff[j+1] -= 3又意味著對(duì)于nums[j+1..]所有元素再減 3，那綜合起來(lái)，是不是就是對(duì)nums[i..j]中的所有元素都加 3 了？

只要花費(fèi) O(1) 的時(shí)間修改diff數(shù)組，就相當(dāng)于給nums的整個(gè)區(qū)間做了修改。多次修改diff，然后通過(guò)diff數(shù)組反推，即可得到nums修改后的結(jié)果。

現(xiàn)在我們把差分?jǐn)?shù)組抽象成一個(gè)類，包含increment方法和result方法：

//差分?jǐn)?shù)組工具類
classDifference{
//差分?jǐn)?shù)組
privateint[]diff;

/*輸入一個(gè)初始數(shù)組，區(qū)間操作將在這個(gè)數(shù)組上進(jìn)行*/
publicDifference(int[]nums){
assertnums.length>0;
diff=newint[nums.length];
//根據(jù)初始數(shù)組構(gòu)造差分?jǐn)?shù)組
diff[0]=nums[0];
for(inti=1;i1];
}
}

/*給閉區(qū)間[i,j]增加val（可以是負(fù)數(shù)）*/
publicvoidincrement(inti,intj,intval){
diff[i]+=val;
if(j+11]-=val;
}
}

/*返回結(jié)果數(shù)組*/
publicint[]result(){
int[]res=newint[diff.length];
//根據(jù)差分?jǐn)?shù)組構(gòu)造結(jié)果數(shù)組
res[0]=diff[0];
for(inti=1;i1]+diff[i];
}
returnres;
}
}

這里注意一下increment方法中的 if 語(yǔ)句：

publicvoidincrement(inti,intj,intval){
diff[i]+=val;
if(j+11]-=val;
}
}

當(dāng)j+1 >= diff.length時(shí)，說(shuō)明是對(duì)nums[i]及以后的整個(gè)數(shù)組都進(jìn)行修改，那么就不需要再給diff數(shù)組減val了。

算法實(shí)踐

首先，力扣第 370 題「區(qū)間加法」 就直接考察了差分?jǐn)?shù)組技巧：

那么我們直接復(fù)用剛才實(shí)現(xiàn)的Difference類就能把這道題解決掉：

int[]getModifiedArray(intlength,int[][]updates){
//nums初始化為全0
int[]nums=newint[length];
//構(gòu)造差分解法
Differencedf=newDifference(nums);

for(int[]update:updates){
inti=update[0];
intj=update[1];
intval=update[2];
df.increment(i,j,val);
}

returndf.result();
}

當(dāng)然，實(shí)際的算法題可能需要我們對(duì)題目進(jìn)行聯(lián)想和抽象，不會(huì)這么直接地讓你看出來(lái)要用差分?jǐn)?shù)組技巧，這里看一下力扣第 1109 題「航班預(yù)訂統(tǒng)計(jì)」：

函數(shù)簽名如下：

int[]corpFlightBookings(int[][]bookings,intn)

這個(gè)題目就在那繞彎彎，其實(shí)它就是個(gè)差分?jǐn)?shù)組的題，我給你翻譯一下：

給你輸入一個(gè)長(zhǎng)度為n的數(shù)組nums，其中所有元素都是 0。再給你輸入一個(gè)bookings，里面是若干三元組(i,j,k)，每個(gè)三元組的含義就是要求你給nums數(shù)組的閉區(qū)間[i-1,j-1]中所有元素都加上k。請(qǐng)你返回最后的nums數(shù)組是多少？

PS：因?yàn)轭}目說(shuō)的n是從 1 開始計(jì)數(shù)的，而數(shù)組索引從 0 開始，所以對(duì)于輸入的三元組(i,j,k)，數(shù)組區(qū)間應(yīng)該對(duì)應(yīng)[i-1,j-1]。

這么一看，不就是一道標(biāo)準(zhǔn)的差分?jǐn)?shù)組題嘛？我們可以直接復(fù)用剛才寫的類：

int[]corpFlightBookings(int[][]bookings,intn){
//nums初始化為全0
int[]nums=newint[n];
//構(gòu)造差分解法
Differencedf=newDifference(nums);

for(int[]booking:bookings){
//注意轉(zhuǎn)成數(shù)組索引要減一哦
inti=booking[0]-1;
intj=booking[1]-1;
intval=booking[2];
//對(duì)區(qū)間nums[i..j]增加val
df.increment(i,j,val);
}
//返回最終的結(jié)果數(shù)組
returndf.result();
}

這道題就解決了。

還有一道很類似的題目是力扣第 1094 題「拼車」，我簡(jiǎn)單描述下題目：

你是一個(gè)開公交車的司機(jī)，公交車的最大載客量為capacity，沿途要經(jīng)過(guò)若干車站，給你一份乘客行程表int[][] trips，其中trips[i] = [num, start, end]代表著有num個(gè)旅客要從站點(diǎn)start上車，到站點(diǎn)end下車，請(qǐng)你計(jì)算是否能夠一次把所有旅客運(yùn)送完畢（不能超過(guò)最大載客量capacity）。

函數(shù)簽名如下：

booleancarPooling(int[][]trips,intcapacity);

比如輸入：

trips=[[2,1,5],[3,3,7]],capacity=4

這就不能一次運(yùn)完，因?yàn)?code style="margin-right:2px;margin-left:2px;padding:2px 4px;font-size:inherit;line-height:inherit;color:rgb(233,105,0);background:rgb(248,248,248);">trips[1]最多只能上 2 人，否則車就會(huì)超載。

相信你已經(jīng)能夠聯(lián)想到差分?jǐn)?shù)組技巧了：trips[i]代表著一組區(qū)間操作，旅客的上車和下車就相當(dāng)于數(shù)組的區(qū)間加減；只要結(jié)果數(shù)組中的元素都小于capacity，就說(shuō)明可以不超載運(yùn)輸所有旅客。

但問(wèn)題是，差分?jǐn)?shù)組的長(zhǎng)度（車站的個(gè)數(shù)）應(yīng)該是多少呢？題目沒有直接給，但給出了數(shù)據(jù)取值范圍：

0<=?trips[i][1]?

booleancarPooling(int[][]trips,intcapacity){
//最多有1000個(gè)車站
int[]nums=newint[1001];
//構(gòu)造差分解法
Differencedf=newDifference(nums);

for(int[]trip:trips){
//乘客數(shù)量
intval=trip[0];
//第trip[1]站乘客上車
inti=trip[1];
//第trip[2]站乘客已經(jīng)下車，
//即乘客在車上的區(qū)間是[trip[1],trip[2]-1]
intj=trip[2]-1;
//進(jìn)行區(qū)間操作
df.increment(i,j,val);
}

int[]res=df.result();

//客車自始至終都不應(yīng)該超載
for(inti=0;iif(capacityreturnfalse;
}
}
returntrue;
}