一文读懂差分数组~

差分数组

---

一、数据结构♎️

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

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

二、使用场景♐️

我们想想这样一个场景：

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

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

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

三、代码实现🕉

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

LC6178. 将区间分为最少组数

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

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

下面看看一个经典差分

LC 2381. 字母移位 II

这题的问题在于，如果是做正常的循环赋值的话，会TLE，所以需要借助`差分数组`来实现简化赋值。

# 全是赋值运算！
# 正常算的话，会超时

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)])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19