差分数组题目

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。

航班预订统计

链接

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        //对区间加法 用差分数组
        int[]diff=new int[n+2];
        for(int[]e:bookings){
            int left=e[0];
            int right=e[1];
            int val=e[2];
            //在[left,right]区间上+val,diff[left]+val,diff[right+1]-val
            diff[left]+=val;
            diff[right+1]-=val;
        }
        int[] answer=new int[n];
        answer[0]=diff[1];
        for(int i=1;i<n;i++){
            answer[i]=answer[i-1]+diff[i+1];
        }
        return answer;
    }
}

拼车

链接

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        //先找出最大的to
        int maxTo=0;
        for(int[]e:trips){
            maxTo=Math.max(maxTo,e[2]);
        }
        //一共有[0,maxTo]个地方 写成[1,maxTo+1]编号
        int[]diff=new int[maxTo+3];
        for(int[]e:trips){
            int left=e[1]+1;
            int right=e[2];//注意这里不用+1,因为在e[2]+1位置下车,相当暂时没人了
            int val=e[0];
            //在编号为[left,right]上加val
            diff[left]+=val;
            diff[right+1]-=val;
        }
        //还原 看看有没有>capacity的
        int cur=0;
        for(int i=1;i<=maxTo+1;i++){
            cur+=diff[i];
            if(cur>capacity){
                return false;
            }
        }
        return true;
    }
}