博客

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {

        int[] nums = new int[n];
        Difference df = new Difference(nums);

        //数组索引从0开始，所以要减1
        for(int[] update : bookings){
            int i = update[0] - 1;
            int j = update[1] - 1;
            int val = update[2];
            df.increment(i,j,val);
        }
        return df.result();
    }
}

class Difference{

    private int[] diff;

    public Difference(int[] nums){
        assert nums.length > 0;
        diff = new int[nums.length];

        //初始化数组构造差分数组[0,nums.length-1]
        diff[0] = nums[0];
        for(int i = 1;i < nums.length;i++){
            diff[i] = nums[i] - nums[i-1];
        }
    }

    //给闭区间处理数据
    public void increment(int i,int j,int val){
        diff[i] += val;
        if(j+1 < diff.length){
            //从j+1开始
            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;
    }
}

执行用时：5 ms, 在所有 Java 提交中击败了42.00%的用户

内存消耗：55.1 MB, 在所有 Java 提交中击败了93.31%的用户

通过测试用例：63 / 63