目录
简介
差分数组
与前缀和数组类似，差分数组里的每个元素，是原数组的后项与前项之差，即：
\[diff[i] = \begin{cases} nums[0], & i = 1\\ nums[i] - nums[i - 1], & i \geq 1\\ \end{cases} \]如果已知差分数组，即可反推出原数组，即
\[nums[i] = diff[i] + nums[i - 1] \]例如，设原数组\(nums = [1, 2, 3, 4, 5, 6, 7, 8]\)，那么：
- 差分数组d的计算方法：
diff[0] = nums[0]
for i in range(1, len(nums)):
diff[i] = nums[i] - nums[i - 1]
- 通过差分数组反推原始数组：
results = [0 for _ in range(len(diff))]
results[0] = diff[0]
for i in range(1, len(diff)):
results[i] = results[i - 1] + diff[i]
上述过程，其实就是在对\(diff\)数组的前缀和的过程。
性质
它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或多次询问某一位的数。
它主要适用于频繁对原始数组的某个区间内的所有元素进行增减。
例如，对区间 \(nums[i:j]\) 所有元素加 \(k\)，那么只需两步：
- 要对 \(diff[i]\ +=\ k\)，然后再对 \(diff[j + 1]\ -=\ k\) ；
- 最后对 \(diff\) 求一遍前缀和即可。
通过差分数组，可以快速对区间进行增加的操作。
总结
差分数组工具类
差分算法，我们可以将其总结为一个工具类：
from typing import List
class Difference(object):
def __init__(self):
self.diff = list()
def build(self, nums: List[int]):
self.diff = [0] * len(nums)
self.diff[0] = nums[0]
for i in range(1, len(nums)):
self.diff[i] = nums[i] - nums[i - 1]
def increase(self, i: int, j: int, value: int):
self.diff[i] += value
if j + 1 < len(self.diff):
self.diff[j + 1] -= value
def result(self) -> List[int]:
result = [0] * len(self.diff)
result[0] = self.diff[0]
for i in range(1, len(self.diff)):
result[i] = result[i - 1] + self.diff[i]
return result
应用
应用1：Leetcode.1109
题目
题目分析
原题可以转换为给定长度为 \(n\) 的数组 \(nums\)，依次对区间 \([left,\ right]\) 里面的每一个元素增加 \(seats\)，最后求修改后的数组。
代码实现
class Solution:
def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
""" 航班预订统计 """
nums = [0] * n
df = Difference()
df.build(nums)
for booking in bookings:
# 注意：由于航班号是从1开始的，所以索引序号需要减一
i = booking[0] - 1
j = booking[1] - 1
value = booking[2]
df.increase(i, j, value)
return df.result()
应用2：Leetcode.370
题目
题目分析
为了求操作之后的数组，我们只需要对差分数组求前缀和，就可以得到原始数组。
代码实现
class Solution:
def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
nums = [0] * length
df = Difference()
df.build(nums)
for update in updates:
df.increase(update[0], update[1], update[2])
return df.result()
应用3：Leetcode.1094
题目
题目分析
将行程中的公里数看成位置坐标，只需要记录有上下客的每个里程区间内的乘客数量，最后再求出乘客数最大的区间，看是否满足汽车的空位即可。
很明显，上下乘客的过程，就可以对区间做增加的过程，所以，直接利用差分数组的性质，计算差分数组，再通过差分数组，反推出原数组即可。
代码实现
MAX_MILE = 1001
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
nums = [0] * MAX_MILE
df = Difference()
df.build(nums)
for trip in trips:
# 由于乘客在trip[2]就下车了，所以实际乘客在车上的旅程为[trip[1], trip[2]-1]
df.increase(trip[1], trip[2] - 1, trip[0])
return max(df.result()) <= capacity