1109.航班预订统计

题目内容

https://leetcode.cn/problems/corporate-flight-bookings/description/

思路讲解

仔细阅读完题目后我们发现题意很清晰，通过累加不同记录的booking来获得总座位数。

你的直觉肯定是先定义一个空数组，遍历bookings这个二维数组，取出每个booking从first遍历到last，途中经过的位置都去加上seats。这是一个可行的方法，也是我一开始想的暴力解法，但这种方法在数据量增大时复杂度会指数级增加。

所以方法需要优化，这里我们引入一种区间同步加和的另一种方式——差分。

什么是差分？

假设我们有一个长度为5空数组，[0,0,0,0,0],我们现在要把1到3索引都加10，应该得到[0,10,10,10,0]。

我们的惯性思维是数组只能存贮固定的数据，但其实数组还可以表示变化。

假设你想看7月的每天最高温度，你发现从1号到20号最高温都是30度，21号到30号最高温都是35度，你去对别人讲肯定会说前20天都是30度，21号开始升温5度，注意你此时的描述就是一个变化，而不是关注数组本身。

还是以[0,0,0,0,0]为例，1到3索引+10还可以怎么理解它的变化？本来全是0,1索引加10，2,3索引相对于1索引都没变化，因为都是加10嘛，所以记录0，直到4索引-10，就表示从4索引开始就不再加了。

于是出现了这样一个记录变化的数组[0,10,0,0,-10],那么怎么得到我们想要的[0,10,10,10,0]呢？

这里就引入了前一章讲过的前缀和，因为前缀和本质还是对状态的叠加，对记录变化的数组计算前缀和，就得到了答案。

用变化代替数据，这就是差分的核心思想

以下是代码实现

代码实现

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] nums=new int[n+1];
        int[] res=new int[n];
        for(int i=0;i<bookings.length;i++){
            int l=bookings[i][0]-1;
            int r=bookings[i][1];
            nums[l]+=bookings[i][2];
            nums[r]-=bookings[i][2];
        }
 
        res[0]=nums[0];
        for(int i=1;i<n;i++){
            res[i]=nums[i]+res[i-1];
        }
        return res;
    }
}

如果对你有帮助记得点赞支持！