1. 差分数组简介

前缀和数组使用与数组中的元素不改变的情况，而差分数字与之相反，适用于数组元素经常改变的情况。比如存在一个数组nums, 给定一个区间[i,j],在给定一个属val,val值可正可负，将区间[i,j]内的元素都加上val, 反复进行如上操作，求解数组中最后的元素值是多少
diff[i]=nums[i]-nums[i-1] 特别注意的一点是diff[0]=nums[0] 之所以设置diff[0]=nums[0]，是因为后面我们需要通过差分数组反推出数组

for(int i=1;i<nums.length;i++)
{
    nums[0]=diff[0];
    nums[i]=nums[i-1]+diff[i];
}

假设现在给出一个区间[i,j]，并给出一个数字3，我们只需要将diff[i]+3, 将diff[j+1]-3，即可达到将区间[i,j]内的元素值都加上3的效果

2. 差分数组实战1

图片.png

这一题本质上是一个差分数组的模板题，特殊点：原始数组nums中元素都是0，每次加的值都是正数

直接套用模板

class Solution {
 int []diff;
 int []nums;
 public int[] corpFlightBookings(int[][] bookings, int n) {
     diff=new int[n];
     nums=new int[n];
     for(int []booking:bookings)
     {
         int i=booking[0]-1;//位置和下标差1
         int j=booking[1]-1;
         int val=booking[2];
         increase(i,j,val);
     }
     getResult();
     return nums;
 }
 public void createDiff(int []nums)
 {
    diff[0]=nums[0];
    for(int i=1;i<nums.length;i++)
     diff[i]=nums[i]-nums[i-1];
 }
 public void increase(int i,int j,int val)
 {
     diff[i]+=val;
     if(j+1<nums.length)
         diff[j+1]-=val;
 }
 public void getResult()
 {
     nums[0]=diff[0];
     for(int i=1;i<nums.length;i++)
     {
         nums[i]=nums[i-1]+diff[i];
     }
 }
}
//O(m+n)  O(m)是处理预定记录  O(n)是反推原数组
//O(n)  保存原来数组的空间消耗

优化空间

对于上面的代码可以省去nums数组，由于原始数组元素都是0，所以差分数组的初始值都是0，其实对于一般情况，最后用差分数组来替代nums数组也是可以的，因为 nums[0]=diff[0] diff[0] nums[1]=nums[0]+diff[1] diff[1]=diff[0]+diff[1] nums[2]=nums[1]+diff[2] diff[2]=diff[1]+diff[2]

class Solution {
    int []diff;
    public int[] corpFlightBookings(int[][] bookings, int n) {
        diff=new int[n];
        for(int []booking:bookings)
        {
            int i=booking[0]-1;
            int j=booking[1]-1;
            int val=booking[2];
            increase(i,j,val);
        }
        getResult();
        return diff;
    }
    // public void createDiff(int []nums)
    // {
    //    diff[0]=nums[0];
    //    for(int i=1;i<nums.length;i++)
    //     diff[i]=nums[i]-nums[i-1];
    // }
    public void increase(int i,int j,int val)
    {
        diff[i]+=val;
        if(j+1<diff.length)
            diff[j+1]-=val;
    }
    public void getResult()
    {
        for(int i=1;i<diff.length;i++)
        {
            diff[i]=diff[i-1]+diff[i];
        }
    }
}
//O(m+n)  O(m)是处理预定记录  O(n)是反推原数组
//O(1)  保存答案的数组不纳入空间消耗

3. 差分数组实战2

图片.png

记上车地点为i，下车地点为j, 人数为val, 实质上就是在区间[i,j-1]范围内对数组加上val(原始数组值都是0)，在进行了所有区间的操作之后，只需要判断数组中的每一个元素是否大capacity, 只要有一个大于capacity就超载

class Solution {
    int diff[]=new int[1000];//车站数目不超过1000
    //最初的状态车是空的 可以看成在各个车站时车站上面的都是空的 因此nums数组为0
    //可以不考虑nums数组
    public boolean carPooling(int[][] trips, int capacity) {
        for(int []trip:trips)
        {
            int val=trip[0];
            //因为trip[2]时已经下车 所以可以看成在区间[trip[1],trip[2]-1]增加人数
            int i=trip[1];
            int j=trip[2]-1;
            increase(i,j,val);
        }
        getResult();
        //最后要求达到每一站时都不能超载
        for(int i=0;i<diff.length;i++)
            if(diff[i]>capacity)
                return false;
        return true;
    }
    public void increase(int i,int j,int val)
    {
        diff[i]+=val;
        if(j+1<diff.length)
            diff[j+1]-=val;
    }
     public void getResult()
    {
        for(int i=1;i<diff.length;i++)
        {
            diff[i]=diff[i-1]+diff[i];
        }
    }
}
//O(n)
//O(n)