小而美的算法技巧：差分数组 :: labuladong的算法小抄

[labuladong]

文章链接点这里：小而美的算法技巧：差分数组

评论礼仪 见这里，违者直接拉黑。

[deepbreath373]

• 又是学废（bushi）了的一天

[Francis730]

倒霉了，一遍没看懂/(ㄒoㄒ)/~~

[FrankYufeiYang]

其实这个和上一篇文章前缀和一点关系都没有。但是被放在了一起比较导致了阅读的时候潜意识老被前缀和误导。。所以第一遍我也没读懂

[lumaster]

0 <= trips[i][1] < trips[i][2] <= 1000
不应该是最多 1001 个车站么?

[labuladong]

@lumaster 感谢指出，文中写错了，我改下

[zhongweiLeex]

倒霉了，一遍没看懂/(ㄒoㄒ)/~~

多看几遍 上手敲一敲 （自己敲） 理解逻辑 加油！

[Alwin4Zhang]

好啊，还能刷到收费的题目，赚了赚了，我说我在lc插件和力扣翻了一会儿没看到这题

[dmzlingyin]

佩服这些设计者的脑子，我可能一辈子都想不到这么秒的方法。

[zhyozhi]

这里的原数组 nums 对应的就是前缀和数组 prefixSum，差分数组 diff 对应的就是前缀和中的原数组 nums。
因此对于假前缀和数组第 [i,j] 位的加减操作，就可以理解为对原数组第 i 位加减某个数，第 j+1 位进行相反操作，就可以使前缀和数组表现为第 [i, j] 位同时加减某个数

[huahuablog]

打卡1

[jay-zhu]

如果trips = [[9,0,1]], capacity = 4
这情况应该是false. 因为一开始就不能进9个人. 所以应该多加一个检查
if (val > capacity) {
return false;
}

[labuladong]

@jay-zhu 可以，但也不是必须的，最后那个 for 循环会统一检查。

[hq22-q]

有点懵

[x43125]

看到最多1001的时候震惊了，我竟然用双循环找最大值

[zhongweiLeex]

区间[i,j]增加 val

但是差分数组 一起增大的 差分数组中间不变（a + val - b-val） == a-b

只是差分数组的第一个和最后一个 这两个元素不同

i位置元素 diff[i] = diff[i] + val

j位置后面元素 diff[j+1] = diff[i+1] - val

[xiaoyuan0203]

这里是不是应该注释一下，nums[i] 表示 站点 i 到站点 i+1 之间的乘客人数。由此，虽然有1001个站点，但是 nums 的长度只要 1000 就可以了。

[LilJessHumble]

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> diff(1001,0); // 建立差分数组
        for(auto vec : trips){
            int passengerNum = vec[0];
            int i = vec[1];
            int j = vec[2];
            diff[i] += passengerNum; // 在第i站有passengerNum人上车
            diff[j] -= passengerNum; // 在第j站有passengerNum人下车
        }
        for(int i=0;i<diff.size();i++){
            if(i){
                diff[i]+=diff[i-1]; // 差分数组的前缀和就是原数组，还原数组得到每个站的人数
            }
            if(diff[i]>capacity) // 若有站的人数大于座位，即表示不可以
                return false;
        }
        return true;
    }
};

发现原来差分数组的前缀和就是原数组！！ 其实区间问题可以不用-1，因为你在vec[ 2 ]-1之后 又在后面修改判断 j+1 是不是越界，然后又让 j+1
理解含义是 在第i站有几个人上车，那就加几个人，第j站有几个人下车，那就减几个人，因为+ 和 - 都包括了当前站点的人数

[yezire]

打卡d5

[shurui91]

1109题我感觉你说的还是挺明白的，但是1094拼车那道题第 trip[2] 站乘客已经下车 那个下标我就有点晕了。感觉题意玩了个文字游戏，说放下乘客的位置是 to，意思其实是这一批乘客还在车上的范围是[from, to - 1]

[labuladong]

我觉得题目挺合理的，第 1 站上车第 5 站下车，那么就是 1~4 站在车上喽。

[CarlLy7]

打卡，附上详细代码

//拼车的代码
    //定义的一个差分数组类，这个类里面主要包括两个主要的方法，一个是更新数组中一个范围的数，另一个方法是返回更新后的数组的结果
    class Difference {
        //差分数组
        private int[] diff;

        public Difference(int[] nums) {
            int n=nums.length;
            if(n<=0){
                return;
            }
            //构造差分数组
            diff=new int[n];
            diff[0]=nums[0];
            for (int i = 1; i <n ; i++) {
                diff[i]=nums[i]-nums[i-1];
            }
        }

        //在i-j这个范围内，对数据进行val更新操作，val可以是负值
        public void incr(int i,int j,int val){
            diff[i]+=val;
            //如果j+1超过了数组的范围说明我们是对i到最后的位置进行了更新，所以j后面的就不需要再减val了
            if(j+1<diff.length){
                diff[j+1]-=val;
            }
        }

        //返回更新后的数组
        public int[] result(){
            int[] res=new int[diff.length];
            res[0]=diff[0];
            for (int i = 1; i < diff.length ; i++) {
                res[i]=res[i-1]+diff[i];
            }
            return res;
        }
    }
    public boolean carPooling(int[][] trips, int capacity) {
        int[] nums=new int[1001];
        Difference difference=new Difference(nums);
        for (int[] trip : trips) {
            int i=trip[1];
            //这里为什么减一，因为到了j位置的时候旅客就下车了
            int j=trip[2]-1;
            //上车的人数
            int val=trip[0];
            difference.incr(i,j,val);
        }
        int[] result = difference.result();
        for (int i = 0; i < result.length; i++) {
            //我们必须保证在开车的整个过程中，车上的人数不能超过最大载客量也就是capacity
            if(result[i]>capacity){
                return false;
            }
        }
        return true;
    }
//=========================飞机的代码
    //定义的一个差分数组类，这个类里面主要包括两个主要的方法，一个是更新数组中一个范围的数，另一个方法是返回更新后的数组的结果
    class Difference {
        //差分数组
        private int[] diff;
        
        public Difference(int[] nums) {
            int n=nums.length;
            if(n<=0){
                return;
            }
            //构造差分数组
            diff=new int[n];
            diff[0]=nums[0];
            for (int i = 1; i <n ; i++) {
                diff[i]=nums[i]-nums[i-1];
            }
        }

        //在i-j这个范围内，对数据进行val更新操作，val可以是负值
        public void incr(int i,int j,int val){
            diff[i]+=val;
            if(j+1<diff.length){
                diff[j+1]-=val;
            }
        }

        //返回更新后的数组
        public int[] result(){
            int[] res=new int[diff.length];
            res[0]=diff[0];
            for (int i = 1; i < diff.length ; i++) {
                res[i]=res[i-1]+diff[i];
            }
            return res;
        }
    }
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] nums=new int[n];
        Difference difference=new Difference(nums);
        for (int[] booking : bookings) {
            //题目中描述下标从1开始，因为数组下标从0开始，所以我们要减1
            int i=booking[0]-1;
            int j=booking[1]-1;
            int val=booking[2];
            difference.incr(i,j,val);
        }
        return difference.result();
    }

[strTian]

拼车最后遍历长度为1001的result，其实后边有很多都是0，加一个全局变量记录一下最后下车位置，就不用遍历所有车站了，代码如下

public int length = 0;
boolean carPooling(int[][] trips, int capacity) {
    // 最多有 1001 个车站
    int[] nums = new int[1001];
    // 构造差分解法
    Difference df = new Difference(nums);
    
    for (int[] trip : trips) {
        // 乘客数量
        int val = trip[0];
        // 第 trip[1] 站乘客上车
        int i = trip[1];
        // 第 trip[2] 站乘客已经下车，
        // 即乘客在车上的区间是 [trip[1], trip[2] - 1]
        int j = trip[2] - 1;
        // 进行区间操作
        df.increment(i, j, val);
        length = Math.max(length, right);
    }
    
    int[] res = df.result();
    
    // 客车自始至终都不应该超载
    for (int i = 0; i <= length; i++) {
        if (capacity < res[i]) {
            return false;
        }
    }
    return true;
}

[JeanYang2]

1094.拼车 python打卡

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        nums=[0]*1001
        df=Difference(nums)

        for trip in trips:
            num=trip[0]
            start=trip[1]
            end=trip[2]-1

            df.increment(start,end,num)
            res=df.result()

            for r in res:
                if r>capacity:
                    return False
        return True

class Difference():
    def __init__(self,nums:List[int]):
        self.nums=nums
        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 increment(self,i,j,val):
        self.diff[i]+=val
        if (j+1)<len(self.diff):
            self.diff[j+1]-=val 

    def result(self):
        res=[0]*len(self.diff)
        res[0]=self.diff[0]
        for i in range(1,len(self.nums)):
            res[i]=res[i-1]+self.diff[i]
        return res

[JeanYang2]

1109.航班预定统计 python打卡

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        nums=[0]*n
        df=Difference(nums)

        for booking in bookings:
            first=booking[0]
            last=booking[1]
            seat=booking[2]

            df.increment(first-1,last-1,seat)
        res=df.result()
        return res


class Difference():
    def __init__(self,nums:List[int]):
        self.nums=nums
        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 increment(self,i,j,val):
        self.diff[i]+=val
        if (j+1)<len(self.diff):
            self.diff[j+1]-=val
        
    def result(self):
        res=[0]*len(self.diff)
        res[0]=self.diff[0]
        for i in range(1,len(self.diff)):
            res[i]=res[i-1]+self.diff[i]
        return res

[xinlanfeng]

diff = [0] * len(nums)
# 构造差分数组
diff[0] = nums[0]
for i in range(1, len(nums)):
    diff[i] = nums[i] - nums[i - 1]

   # 从这里可以直接反推出得到原始数组的等式
   # nums[i] = diff[i] + nums[i-1]

由等式 nums[i] = diff[i] + nums[i-1] 可得：

• 如果 diff[i]的值+3, 则nums[i]的值就增加了3，同时，i之后的元素，如nums[i+1] = diff[i+1] + nums[i]，由于nums[i]的值已经增加了3，所以nums[i+1]的值也会增加3

• 所以，如果diff[i]的值增加3，则nums[i]及之后的所有元素的值都会增加3

• 同理可得，如果diff[j+1]的值减小3，则nums[j+1]及之后的所有元素的值都会减小3

• 所以，如果nums[i..j]的元素的值需要增加val, 则只需让 diff[i] += val, diff[j+1] -= val即可

[fangyuan99]

对于各类「区间求和」问题（加粗字体为最佳方案）：

数组不变，区间查询：前缀和、树状数组、线段树；
数组单点修改，区间查询：树状数组、线段树；
数组区间修改，单点查询：差分、线段树；
数组区间修改，区间查询：线段树。
本题只涉及「区间修改 + 单点查询」，属于「区间求和」问题中的入门难度。

对于各类「区间求和」问题，该用什么方式进行求解，之前在 这里 提到过。
作者：宫水三叶
链接：https://leetcode.cn/problems/corporate-flight-bookings/solutions/968467/gong-shui-san-xie-yi-ti-shuang-jie-chai-fm1ef/
来源：力扣（LeetCode）

[YANLING-H]

计算累加和大佬写错了吧：

// 计算 nums 的累加和
for (int i = 1; i < preSum.length; i++) {
preSum[i] = preSum[i - 1] + nums[i - 1];
}

应该是下面这样写吧， 要不然preSum数组没有填满
// 计算 nums 的累加和
for (int i = 1; i < preSum.length + 1; i++) {
preSum[i] = preSum[i - 1] + nums[i - 1];
}

[llxblhyvia]

注意点：飞机那道题的下标是从1开始的，大巴车的下标是从0开始的！

[fear666]

拼车

内存优化
东哥的写法比较简单粗暴直接，直接根据提示中的0 <= fromi < toi <= 1000去构造了长度为1001的数组

其实可以先遍历一遍trips找到测试用例中最大的toi，构造长度为最大toi+1的数组，因为最大toi之后车子是空载的。

虽然多遍历了一遍trips，但后续“判断每公里是否超载”的时候，数组长度小了>遍历次数少了，时间也会适当地减少。

[liujiawen0905]

当 j+1 >= diff.length 时，说明是对 nums[i] 及以后的整个数组都进行修改，那么就不需要再给 diff 数组减 val 了。请问这句话怎么理解不太懂

[SkyeKD]

可以计算出最大的下客车站，len就用最大的下客车+1.这样可以节省空间，时间反而更快

[flashlight-byte]

为啥文章代码里面创建df对象时候只传递了一个参数？
Difference df(nums);
不是还需要长度信息吗？