差分数组 - 对区间内元素的统一操作

目录

概念

题单

1 拼车

2 将区间分为最少组数

3 字母移位

4 使数组中的所有元素都等于零

5 零数组变换Ⅰ

6 最大化城市的最小电量

---

概念

差分数组，顾名思义，就是由原数组的相邻元素作差而得到的差值组成的新的数组。

对于原数组 a = [ 1 , 3 , 5 , 7 , 13 , 17]

他的差分数组 diff 的定义如下：  d[0] = a[0] , d[i] = a[i] - a[i-1] 

那么上述的 a 的差分数组 diff = [1 , 2 , 2 , 2 , 6 , 4]

那么差分数组有什么性质呢？由于差分数组的每个值都是原数组对应位置的值与前一个值的差值，那么我们只要知道前一个值，加上差分数组中的差值就能得到本位置的值，同时由于我们差分数组的第一个元素就是原数组的首元素，那么我们可以根据第一个位置的值以及后续的差值，根据差分数组求出原数组的每一个位置的值。

我们定义差分数组的前缀和 prev[i] 表示差分数组的 [0,i] 区间的元素之和，那么上述差分数组的前缀和数组如下：  prev = [1 , 3 , 5 , 7 , 13 , 17] ，而我们能够发现差分数组的前缀和数组就是原数组。

性质一 ： 差分数组的前缀和数组，能够还原原数组

差分数组还有什么特殊的呢？

假设我们对原数组 a 的a[i] , a[2] , a[3] 都加上一个相同的数 x ，那么很简单，a = [1 , 3 + x , 5  + x, 7 + x , 13 , 17];

那么差分数组 diff = [1 , 2 + x , 2 , 2 , 6 - x , 6] 。

我们能够发现，对原数组的一个区间内 [l,r] 的所有元素都加上相同的值x（x可以是正数也可以是负数）之后，差分数组中，只有 diff[l] 和 diff[r+1] 发生变化，因为在[l,r]区间内的元素的差值并不会发生改变。

性质二：对原数组 [i , j] 区间的所有元素都加上 x ，等价于对差分数组的 d[i] 加上x，以及对 d[j+1] - x

那么根据性质一和性质二，我们能够根据差分数组还原出原数组，同时能够将对原数组的区间操作转换为对差分数组的少量元素的操作，那么我们就能够使用差分数组来完成一些类似于对数组的某个区间进行统一操作的问题，更加简单方便。

我们可以利用差分数组的性质来完成以下几个经典题目：

题单

1 拼车

1094. 拼车 - 力扣（LeetCode）https://leetcode.cn/problems/maximize-the-minimum-powered-city/1094. 拼车 - 力扣（LeetCode）

题目解析： 公交车的座位有 capacity 个，然后给定一个数组 trips,trips[i] 表示一批乘客，这一批的乘客数量为 trips[i][0] , 他们从 trips[i][1] 上车，最终在 trips[i][2] 下车，然后我们需要判断公交车是否能够接送所有的乘客。 其实就是问在整个行驶过程中，会不会超员。

那么我们需要保证行驶过程中每一个时间点，公交车上的人数都不能超过 capacity ，如果超过，就说明公交车座位不够，无法接送所有的乘客。

而每一批乘客在公交车上乘坐的路程是一整段区间，也就是在这段区间内，这批乘客始终需要占据座位，那么其实每一批乘客 trips[i] ，对于公交车上人数的影响就是会使在 [trips[i][1] , trips[i][2] ) 区间内增加 trips[i][0] ， 注意对于 trips[i][2] 的时候，乘客已经下车，所以我们不需要对trips[i][2] 冶金学加法。 其实就是一个区间的加法。

那么我们如果使用差分数组来完成这个题的话就会简单很多，我们初始化 diff 全部为0，表示整个行驶过程没有任何乘客，然后开始遍历 trips[i] 来对差分数组进行操作。

trips[i] 会使公交车上总人数在 [trips[i][1], trips[i][2]) 这个区间内增加 trips[i][0] 人，不会影响trips[i][2]及之后的时间段，所以他对于差分数组的影响就是 ： 

diff[trips[i][1]] += trips[i][0] , diff[trips[i][2]] -= trips[i][0]

细节问题:

我们可以使用一个全局的 diff[1001] 来作为差分数组，全局的数据会在main之前被初始化为0.

最终判断能否接送所有乘客的时候，我们只需要判断在任意时刻，公交车上的人数是否大于座位数就行了，也就是判断所有的前缀和是否大于capacity。

代码如下：

class Solution {
public:int diff[1001];bool carPooling(vector<vector<int>>& trips, int capacity) {for(auto&v:trips) diff[v[1]] += v[0] , diff[v[2]] -= v[0];int prevsum = 0 ; for(auto e : diff){prevsum += e;if(prevsum > capacity) return false;} return true;}
};

2 将区间分为最少组数

2406. 将区间分为最少组数 - 力扣（LeetCode）

解析题目：题目给定一些区间， intervals[i][0] 表示第i个区间的左端点，intervals[i][1] 表示第i个区间的右端点，都是闭区间。

我们需要对所有的区间进行分组，使得在一个分组内的所有区间不能有任何交集。

比如我们有三个区间:  [1, 2 ] ,[ 3 , 4]  , [2 , 3] 

由于 [2,3]会和 [1,2] ，[3,4] 都有交集，所以[2,3] 必须要和这两个区间分开自成一组。 而区间 [1,2],[3,4]没有交集，那么他们可以在同一个组中，那么这三个区间至少需要划分为两个组。

其实本题我们可以转换一下思路：

对于所有的区间，如果有冲突，那么至少是两个区间的冲突，也有可能是更多区间，比如：[1,5],[2,6],[3,7] 这三个区间在 [3,5] 之间冲突了三次，那么这三个区间一定不能在同一个分组中，也就是对于这三个区间至少需要分为三组。

那么我们是不是可以统计每一个值他所冲突的区间个数，在所有的有效值中，冲突区间最多的个数，就是至少需要分组的个数，因为这些区间都在该值有冲突， 无法划分到一个组。

那么对于其他的冲突的位置如何处理？ 不管怎么说，他们的冲突的区间的个数一定是小于等于最大的冲突个数的，那么一定可以分配到各个组中，使得不冲突。

那么我们是不是可以将这个题再转换为上下车的问题。

每一个区间 [l,r] 表示在 [l,r] 范围内有一个乘客乘车，在 l 位置上车，在r+1位置下车，问我们公交车至少需要多少个座位：

那么思路就和上一个题一样了，我们使用差分数组来记录人数数组的差值，最后求出差分数组的前缀和，最大的前缀和就是同一时间最多的乘客数量。

主要本题的区间是闭区间，而 right 的最大值为 1000000，那么最晚下车的时间就有可能是 1000001，我们的差分数组就需要开辟 1000002 个空间。

代码如下：

class Solution {
public:int diff[1000002];int minGroups(vector<vector<int>>& intervals) {for(auto & v : intervals) diff[v[0]]++ , diff[v[1]+1]--;int prevsum = 0 , res = 0;for(auto e : diff){prevsum += e;res = max(res,prevsum);}return res;}
};

当然本题其实就是求区间重叠的最大个数，那么其实也可以按照区间左端点进行升序排序，然后使用堆来记录最大的重叠区间个数。

3 字母移位

2381. 字母移位 II - 力扣（LeetCode）

题目解析： 题目给定一个二维数组，数组中每一个元素 shifts[i] 表示将字符串的一段区间的所有字符进行移位操作。移位操作有两种，当shifts[i][2] = 1时，表示将对应区间的所有字符都向后移一位，当 shifts[i][2] = 0 时，表示将对应区间的所有字符都向前移一位。

如果我们直接对所有的区间进行暴力遍历移位操作，也就是遍历每一个区间，然后对区间每一个字符进行移位操作，那么大概率会超时。因为我们可能会对同一个字符进行多次移位操作，我们可以先累计每一个位置的字符的移位次数，将向前移一位记为 -1 ，向后移一位记为+1，那么最终就会有三种情况，1、对应位置的字符的移位操作 cnt = 0 ，此时我们不需要对这个字符做任何操作。 2、对应字符的移位操作次数  cnt > 0 ，那么此时需要向后移位，但是我们需要将其向后移cnt次吗？并不需要，因为字母表每26个字母是一个循环，所以我们只需要移动 cnt%26次就行了；    3、对应位置的字符的移位操作次数 cnt < 0  ，同时此时我们也只需要向前移 cnt%26 次就行了。

那么现在问题就转换为了每一个位置的字符的移位操作次数是多少？

当 shifts[i][2] == 1 的时候，代表 [shifts[i][0],shifts[i][1]] 区间内的所有字符都需要向后移动1位，那么也就是对于这个区间的字符的移动次数 cnt 都需要进行+1操作。 

当 shifts[i][2] == 0 的时候，代表 [shifts[i][0],shifts[i][1]] 区间内的所有字符都需要向前移动一位，那么也就是相当于这个区间的字符的移动次数 cnt 都需要进行 -1 操作。

那么我们记录所有字符的cnt的化，每一个 shifts[i] 都是再对 cnt 数组进行区间的统一操作，我们显然可以使用差分数组来解决。

首先初始化 diff 的长度为 s 的长度 + 2，同时初始情况下每一个位置的移动次数都为0，那么差分数组的所有值都为0 ，当然本题的数据范围其实s的长度 <= 50000，那么我们可以开 50002 个空间。

然后我们可以遍历每一个区间， shitfs[i][2] == 1 的时候，需要对 cnt  的[shifts[i][0] , shifts[i][1]]的所有元素进行加1操作，那么需要对 diff[shifts[i][0]] + 1,对 diff[shifts[i][1] + 1] -1;

反过来，shitfs[i][2] == 0 的时候，需要对 cnt  的[shifts[i][0] , shifts[i][1]]的所有元素进行减1操作，那么需要对 diff[shifts[i][0]] - 1,对 diff[shifts[i][1] + 1] +1;

统计完差分数组之后，我们就可以是用前缀和来求出所有的位置需要移位的次数。

代码如下：

class Solution {
public:int diff[50002];string shiftingLetters(string s, vector<vector<int>>& shifts) {for(auto& v:shifts){ if(v[2] == 1) ++diff[v[0]], --diff[v[1]+1];else --diff[v[0]] , ++diff[v[1]+1];}int prevsum = 0 ;for(int i = 0 ; i < s.size() ; ++i){prevsum += diff[i];if(prevsum < 0) prevsum += 5200; //将向前移位的操作转换为向后移位操作prevsum %= 26;//由于 'z' = 122 ,那么再进行向后移位的加法的时候可能会溢出if(s[i] + prevsum >= 128) s[i] += (prevsum - 26);else s[i] += prevsum;if(s[i] > 'z') s[i] -= 26;if(s[i] < 'a') s[i] += 26;}return s;}
};

4 使数组中的所有元素都等于零

2772. 使数组中的所有元素都等于零 - 力扣（LeetCode）

题目解析：给定一个数组，我们每一次可以对数组的一个长度为 k 的子数组所有元素进行减1操作，判断最终能否将所有的元素都变成0。

其实要使所有的元素都变为0，那么我们可以从前往后遍历整个数组，要使每一个元素都位0，如果nums[i] < 0 ，那么说明前面元素在变为0的时候，把后面元素变成小于0了，那么此时一定是无法将全部元素都变成0的。 如果 nums[i] 等于0，那么针对nums[i] 就不需要再做变换了。如果nums[i]>0，那么要使nums[i] ==0 ，就还需要让 nums[i] 开始的长度为k的子数组都进行nums[i]次减一操作，那么我们需要将后续k-1个元素都进行减 nums[i] 。 

但是这样一来，我们真的去对长度为k的子数组的每个元素进行减一操作的话，时间复杂度比较高，由于我们是对一个区间进行统一的减一操作，所以我们可以使用差分数组来完成。

要使所有元素都为0，那么差分数组的所有元素也必须为0.

我们可以先根据数组元素初始化差分数组，然后从前往后遍历，不断将 diff[i] 变为0，由于我们是从前往后遍历，遍历到 diff[i] 的时候，diff数组中前面的所有元素都已经变成0，那么我们可以认为经过了前面的转换操作之后，nums[i] = diff[i] ，而我们需要将 nums[i] 变为0，那么 diff[i] -= diff[i] ,diff[i+k] += diff[i]。其实就是相当于对 nums 的[i,i+k] 区间进行了 nums[i] 次减一操作。

如果遍历中途遇到 diff[i] < 0 ，那么我们直接返回 false; 

最终遍历到 n - k , diff[n-k]是一个特殊的位置，我们需要特殊处理，因为[n-k,n-1]这段区间也是一段长度为 k 的区间，但是我们进行减一操作的时候，由于diff只开了nums.size()空间，那么对diff[i+k] 的操作会越界。然后我们需要判断一下diff数组剩余的位置是否全为0，如果是，那么返回 true，否则返回 false。

代码如下：

class Solution {
public:bool checkArray(vector<int>& nums, int k) {int n = nums.size();vector<int> diff(n);diff[0] = nums[0];for(int i = 1; i < n ; ++i) diff[i] = nums[i] - nums[i-1];for(int i = 0 ; i < n - k; ++i){if(diff[i] < 0) return false;diff[i+k] += diff[i];  //对[i,i+k-1]的子区间进行减diff[i]操作，所以 diff[i+k] += diff[i]diff[i] = 0;}//注意，对 nums 的[n-k,n-1]这个区间其实还可以进行操作，因为长度为 k ，但是此时由于我们的diff数组只开了n个空间，那么访问 diff[i+k]会越界，所以我们特殊处理diff[n-k] = 0;    for(int i = n - k  +  1; i < n ; ++i){if(diff[i] != 0) return false;}return true;}
};

5 零数组变换Ⅰ

3355. 零数组变换 I - 力扣（LeetCode）

解析题目：题目给定一个原始数组，有多个查询，每一个查询 queries[i] 表示在[queries[i][0],queries[i][1]] 范围内选定一个下标子集(注意这个下标子集并不要求连续)，让这些下标的值都减一。判断能否在这些查询之后，使得所有的元素都为0.

其实本题很简单，由于nums所有元素都是大于0的，所以我们不需要考虑负数的情况。

我们假定某个位置的元素，在 x 个查询的区间内，那么最多可以对该位置元素进行x次减一操作，那么该位置元素的最小值就是 nums[i] - x ,那么只要 nums[i] - x <= 0，那么就说明nums[i]能够在这些查询的操作下变成0。因为在这种情况下，我们可以选择其中的 nums[i] 个查询对nums[i]进行减1操作，而剩余的包含 i 位置的查询，我们在选择下标子集的时候可以不选 i ，那么nums[i]最终就能够变成0.

那么我们其实只需要求出nums的每个元素可以达到的最小值就行了，如果最小值<=0，那么就可以变为0。 这样一来我们就不需要纠结题目中的下标子集这个问题，而是直接对查询的整个区间进行操作。这样一来，整个查询过程就是一个简单的区间减法问题，使用差分数组就很简单了。

对于每个查询，我们对[l,r]区间都进行减一操作，那么等价于 diff[l] -- ,diff[r+1] ++， 但是由于 r+1可能越界也就是 r+1 = n ,但是由于 diff[n] 无意义，所以我们可以忽略 r+1 ==n 的情况。

class Solution {
public:bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {int n = nums.size();vector<int> diff(n);diff[0] = nums[0];for(int i = 1 ; i < n ; ++i) diff[i] = nums[i] - nums[i-1];for(auto& v: queries){diff[v[0]] --;if(v[1] + 1 < n) diff[v[1] + 1]++; //由于 v[1] 可能为 n-1，那么v[1] + 1就越界，我们不需要关注越界的差分值，没有意义}int prevsum = 0 ;for(auto e: diff){prevsum += e;if(prevsum > 0) return false;}return true;}
};

6 最大化城市的最小电量

2528. 最大化城市的最小电量 - 力扣（LeetCode）

解析题目：首先给定了每个城市的供电站的数量，以及供电站能否辐射的范围，借助这两个条件我们就能够求出所有的城市的电量。 然后我们需要再建 k 个供电站，建完之后，所有城市中最少电量 最大可以是多少？

要使得所有城市中，最小电量最大，按照贪心的思路，我们需要尽可能在原供电站电量的情况下，尽可能将新的供电站建在能否辐射到最小电量城市的范围内，使得这些电量较小的城市的电量变大。

那么这其实是一个单调的问题，要使的最小电量越大，那么就需要新建的供电站越多，我们可以考虑使用二分来解决。

首先第一步我们还是需要求出所有的城市的当前已有电量，我们可以是用前缀和数组来统计，prevsum[i] 表示 第i个城市以及之前一共有多少个供电站，那么我们知道，第i个城市能够被[i-r,i+r]这些城市的供电站提供电量，那么第i个城市的电量就是：prevsum[i+r] - prevsum[i-r-1]。 同时这两个下表都有可能越界，所以我们需要判断一下。

那么我们的电量以及差分数组初始化如下：

    long long maxPower(vector<int>& stations, int r, int k) {int n = stations.size();vector<long long> prevsum(n) ,power(n), diff(n);prevsum[0] = stations[0];for(int i = 1 ; i < n ; ++i){prevsum[i] = stations[i] + prevsum[i-1];}for(int i = 0 ; i < n ; ++i){power[i] = prevsum[((i + r >= n) ? n - 1: i + r)] - (i - r -1 < 0 ? 0 : prevsum[i-r-1]);}diff[0] = power[0];for(int i = 1 ; i < n ; ++i) diff[i] = power[i] - power[i-1];

接下来我们就需要确定最小电量的范围，如果 k 为0  ，那么最小电量的值就是所有城市供电的最小值 mincount，我们需要遍历求出。 而最小电量的最大值为 ： 只有一个城市的电量很小，其他的城市的电量都远大于该城市，差值大于等于 k ，那么此时需要将所有的供电站都辐射给该城市，那么此时最大值就是 ： mincount + k ;

        int mincount = diff[0] , prevsum = 0;for(auto e : diff){prevsum += e;mincount = min(mincount , prevsum);}int left = mincount , right = mincount + k , mid = (left + right) / 2;//闭区间二分，[left,right]

接下来我们就需要考虑二分的思路了。

我们假定最小电量的最大值为 mid ， 那么从前往后遍历每一个城市的电量，当遇到某一个城市的电量 prev[i] <  mid 时，我们需要建供电站使得该城市的电量等于 mid ，那么供电站建在哪呢？从贪心的角度来看，由于 i 之前的所有的城市电量都大于等于mid，i之后的城市我们还不确定，所以我们需要将供电站建在i城市，尽可能去辐射后面的未确定电量的城市,辐射的范围是说明呢？ [i,i+2*r]，需要建的发电站的数量是 mid - prev[i] 。 

那么从前往后遍历的过程中，使得所有的城市的供电量都大于等于 mid 时，所需要的供电站数量如果大于 k ，那么说明无法满足，那么我们需要缩减二分区间, right = mid -1;

如果能够满足，那么 left = mid;

代码如下：

class Solution {
public:bool check(long long mid , vector<long long> diff , int r, long long k){long long prevsum = 0 ;long long cnt = 0;for(int i = 0 ; i < diff.size(); ++i){prevsum += diff[i];if(prevsum < mid){cnt += (mid - prevsum);if(i - r >= 0)diff[i - r] += (mid - prevsum);else diff[0] += (mid - prevsum);if(i + 2*r + 1 < diff.size()) diff[i + 2*r + 1] -= (mid - prevsum);prevsum = mid;if(cnt > k) return false;}}return true;}long long maxPower(vector<int>& stations, int r, int k) {int n = stations.size();vector<long long> prevsum(n) ,power(n), diff(n);prevsum[0] = stations[0];for(int i = 1 ; i < n ; ++i){prevsum[i] = stations[i] + prevsum[i-1];}for(int i = 0 ; i < n ; ++i){power[i] = prevsum[((i + r >= n) ? n - 1: i + r)] - (i - r -1 < 0 ? 0 : prevsum[i-r-1]);}diff[0] = power[0];for(int i = 1 ; i < n ; ++i) diff[i] = power[i] - power[i-1];long long mincount = diff[0] , prev = 0;for(auto e : diff){prev += e;mincount = min(mincount , prev);}long long left = mincount , right = mincount + k , mid = (left + right) / 2;//闭区间二分，[left,right]while(left < right){//判断能否是最小电量达到 midif(right == left + 1){if(check(right,diff,r,k))return right;else return left;}bool ret = check(mid,diff,r,k);if(ret) left = mid;else right = mid - 1;mid = (left + right) / 2; }return left;}
};

总结

差分数组可以用来解决对数组的一个区间进行统一的加法或者减法的问题，只需要修改差分数组的两个位置，而不需要真正遍历这个区间去修改，能够大幅提高效率。同时差分数组的两个性质能让我们利用差分数组的前缀和还原出原数组。