差分数组

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int nums[] = new int[n];
        Difference diff = new Difference(nums);
        for(int i = 0; i < bookings.length; i++){
            //要注意置入数组的索引要减1
            diff.increment(bookings[i][0]-1,bookings[i][1]-1,bookings[i][2]);
        }
        return diff.result();
    }
}

// 差分数组工具类
class Difference {
    // 差分数组
    private int[] diff;
    
    /* 输入一个初始数组，区间操作将在这个数组上进行 */
    public Difference(int[] nums) {
        assert nums.length > 0;
        diff = new int[nums.length];
        // 根据初始数组构造差分数组
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    /* 给闭区间 [i, j] 增加 val（可以是负数）*/
    public void increment(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;
    }
}

差分数组的思想是，保持数组中的元素特性为，后一项记录的是与前一项的差值。这样子就可以保证我们很容易的批量对数组中的数据进行进行增减。

下面的图片就是描述差分数组，以及本题对差分数组的应用。

1094. 拼车 - 力扣（LeetCode）

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        //题目限定条件可知，车站有1001个，从0到1000
        int nums[] = new int[1001];
        Difference diff = new Difference(nums);
        for(int[] trip : trips){
            //由于到站下车了，人就不在那个站了，所以
            diff.increment(trip[1],trip[2]-1,trip[0]);
        }
        int[] res = diff.result();
        for(int r : res){
            if (r > capacity) return false;
        }
        return true;
    }
}

// 差分数组工具类
class Difference {
    // 差分数组
    private int[] diff;
    
    /* 输入一个初始数组，区间操作将在这个数组上进行 */
    public Difference(int[] nums) {
        assert nums.length > 0;
        diff = new int[nums.length];
        // 根据初始数组构造差分数组
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    /* 给闭区间 [i, j] 增加 val（可以是负数）*/
    public void increment(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;
    }
}