差分数组

一、数据结构♎

在讲差分.数组前，我们可以先看一看【前缀和数组】哦

index 0 1 2 3 4
nums 8 2 6 -2 9
diff 8 -6 4 -8 11

我们可以将任意一个数组转化为带有元素之间关系的差分数组，其关系为：

diff[i]= \left\{ \begin{array}\ nums[i]-nums[i-1],i\ne 0 \\ nums[i],i=0 \end{array} \right.

二、使用场景♐

我们想想这样一个场景：

有一个一百万数据量的数组，每次需要对其中连续的九十万个数据量进行同步修改，我们会发现，这样做的时间复杂度是O(Tn)O(Tn)，也就是线性级别，在操作次数过多、数组过大时，会耗费大量的时间。这样在某些业务里是不可接受的。

有没有一种数据结构能够实现对某个区间元素同步进行修改呢？诶，那必须是我们的差分数组啦！！

对于修改区间[i,j][i,j]的值，我们只需要令：diff[i]+=valdiff[i]+=val，也就是进入的时候，海水开始涨潮了，涨潮后，水平面相对不变(不用修改)，但实际高度增加了(进入的临界点)。当然，最后需要令diff[j+1]−=valdiff[j+1]-=val，也就是退潮啦。

我们来看两组差分队列：

1
2
3
4
5
6
7
8
[[1,2],[3,4],[5,6],[7,8]]
# [0, 1, 0, 0, 0, 0, 0, 0, 0]

[[1,2],[2,3],[3,4],[4,5]]
# [0, 1, 1, 0, 0, -1]

[[1,2],[2,3],[3,4],[4,5],[3,5],[3,6],[1,4],[2,7]]
# [0, 2, 2, 2, 0, -2, -2, -1]

三、代码实现🕉️

我们通过一题来看看如何实现吧！

LC6178. 将区间分为最少组数

image-20220912170357166 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
		# 核心在于： 寻找同时重叠的波浪
        # 差分队列
        maxVal=max([i[1] for i in intervals])
        diff=[0]*(maxVal+1) # 0->maxVal

        # 计算区间变化情况
        for i,j in intervals:
            diff[i]+=1 # 涨潮
            if j+1<=maxVal:
                diff[j+1]-=1 # 退潮
        # 查看有多少区间上重叠了
        # 最大值就是重叠的区间数目
        res,t=0,0
        for i in diff:
            t+=i
            res=max(res,t)
        return res

当然并不是所有的区间问题都能用差分求解！差分只是为了简化赋值运算，那么该贪心的时候就贪心，该DP就DP，别老想着别的。

不过如果你说重叠部分，差分确实能够起到一定的效果~

下面看看一个经典差分

LC 2381. 字母移位 II

image-20220912222755301 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 全是赋值运算！
# 正常算的话，会超时


class Solution:
    def shiftingLetters(self, s: str, shifts) -> str:
        diff=[0]*(len(s)+1)
        # 构建差分
        for st,e,shift in shifts:
            diff[st]+=shift*2-1
            diff[e+1]-=shift*2-1
        # 获取移动表
        shift=[]
        for i in diff:
            if shift==[]:
                shift.append(i)
            else:
                shift.append(i+shift[-1])
        # 输出
        return "".join([chr(ord("a")+(ord(i)-ord("a")+dif)%26) for i,dif in zip(s,shift)])