差分算法总结

说到差分算法，就不得不提一个经典的公交车上下车问题：

• 题目描述：给定二维数组，表示公交车每个站点上下车人数
• 问：公交车从起点到终点，车上最多有多少人？或者假如公交车最大载人量为k，问能否将所有人拉到目的地？

类似的问题还有很多，比如拼车问题、会议室问题、日程安排问题等等。

本文首先简单介绍下什么是差分算法，然后给个差分算法的解题模板。最后总结一下leetcode中标准差分应用题，方便大家练习。

差分原理及模板

什么是差分？

差分算法种包含两个数组：真实数组和差分数组，差分算法的名字就取自于“差分数组”。这两个数组定义为：

• 真实数组：a = {a[0], a[1], ..., a[n]}，表示各个点真实数据
• 差分数组：b = {b[0], b[1], ..., b[n]}，表示各个点数据的变更值

所谓变更值，就是和前一个点数据相比，当前值有什么变化。两个数组之间具有如下关联：

• b[0] = a[0], b[i] = a[i] - a[i-1]，即差分数组各点值，为真实数据的变更值
• a[i] = b[0]+b[1]+...+b[i]，差分数组的前缀和 = 真实数组（差分算法核心）
• a[i] = a[i-1] + b[i]，可以从上一个点的真实数据和当前点差分值，推算出当前点真实数据

解题模板

看完上面差分原理，其实挺懵的，就两个数组，和诸如“上下车”问题有啥关系？下面我们通过一个经典例题1094. 拼车来看看如何利用差分算法解题，题目描述如下：

车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）

给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

解题代码如下：

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        //解题思路如下：
        //map记录每个站点的变化，key为站点number，value为站点上下车人数
        //比如<1, 5>，表示在1号站点上车5人，<4, -3>表示在4号站点下车3人
        //该map相当于，我们前面提到的差分数组，表示每个站点车上人数变化
        //那显而易见，真实数组表示的就是每个站点，车上的总人数
        //那问题是不是就是转化成：每个站点车上人数都要小于等于capacity，否则不能将所有乘客送达目的地
        TreeMap<Integer, Integer> map = new TreeMap<>();
        //遍历trips数组
        for(int[] t : trips){
            //起点上车，人数加t[0]
            map.put(t[1], map.getOrDefault(t[1], 0) + t[0]);
            //终点下车，人数减t[0]
            map.put(t[2], map.getOrDefault(t[2], 0) - t[0]);
        }
        int prefix = 0;//前缀和
        //差分数组map前缀和，等于各个站点，真实数组的值，即车上人数
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            prefix += entry.getValue();
            //如果车上人数大于capacity，直接返回false
            if(prefix > capacity)
                return false;
        }
        return true;
    }
}

本例题中，站点总数最多为1000，因此我们也可以用数组代替map。

好了，通过前面例题，我们应该大概了解，如何利用差分算法解决实际问题了。

在实际应用中，通常都是给你变更数据，然后构造差分数组，再求真实数组，用真实数组解题。大致流程为：

1. 初始化差分数组：根据数据变更点构造差分数组，常用map<int, int> （key: 变更点， value：变更值）
2. 根据差分数组求原始数组：对差分数组求前缀和，求出的即为原始数组
3. 根据原始数组判断结果

什么时候用差分

当遇到顺序序列节点，每个节点的值有增有减，就可以考虑使用差分。

不过差分算法，时间复杂度通常为O(n)或者O(n^2)。因此，当时间复杂度要求比较高的时候，就需要使用线段树之类更加复杂的方法。

练习题

1. 1094. 拼车

   给定变更点，先求差分数组，然后前缀后求真实数组，判断每个站点车上人数是否大于最大容量。

2. 1109. 航班预订统计

   解法和“拼车”问题一模一样。

3. 729. 我的日程安排表 I

   用二分可能更快一点，不过用差分也可以

4. 731. 我的日程安排表 II

   同“日程表安排表I”

5. 732. 我的日程安排表 III

   同“日程表安排表I”

打赏