简介

差分数组

与前缀和数组类似，差分数组里的每个元素，是原数组的后项与前项之差，即：

如果已知差分数组，即可反推出原数组，即

例如，设原数组\(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

题目

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

题目

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

题目

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

原文地址：http://www.cnblogs.com/larry1024/p/16897831.html