LeetCode区间问题总结

上周五考试没有过，其中专业级第二题是关于区间的问题，在leetcode上找到类似的题目，总结复习下。

引子

先看这道题，1109. 航班预订统计，题目是这样的

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

我们这儿有一份航班预订表，表中第 i 条预订记录 bookings[i] = [i, j, k] 意味着我们在从 i 到 j 的每个航班上预订了 k 个座位。

请你返回一个长度为 n 的数组 answer，按航班编号顺序返回每个航班上预订的座位数。参考示例如下，

1
2


输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]

解题思路

将这道题的示例画一张表格表示一下，就是下面的结果

booking	1	2	3	4	5
1	10	10	0	0	0
2	0	20	20	0	0
3	0	25	25	25	25
total	10	55	45	25	25

常规思路就是以航班号为基本坐标，计算每一个航班增加的座位数，然后逐项汇总相加即可。

设置初始结果vector<int> res(n, 0);
遍历bookings，每次取其中的航班的预定数，添加到res对应的数组中，比如第1个booking，那么res[0]+=10; res[1]+=10，依次类推，直到遍历截止。

上面的算法比较简单直观，但是可以分析发现，算法的复杂度有点高，两层遍历算法时间复杂度是$O(n^2)$，空间复杂度是$O(n)$不甚理想。

有没有复杂度更简单的思路呢？这里有一个类比公交站的思路，可以将航班号码比作公交站牌，比如1号公交站，2号公交站，假定这些公交站是依次按顺序分布在一条直线公路上，第i个航班的飞机的预定数目就是公交车在第i个公交站发车时候的乘客数目（包括了上车和下车的乘客数）。

举例说明，第1行表示，第1站交车上人数是10，说明公交车行驶到第1站时上车10人，到第2站时候车上的乘客仍然是10人，说明没有乘客上下车，到第3站时候车上乘客0人，说明此时有10人下车。如果使用长度为N的数组count表示每一站上下乘客的变化量(count[i] 表示第i + 1站上下车的乘客变化量），

对于booking = [i,j,k]，

表示在公交站第i站上车k人，count[i - 1] += k；

第i + 1站直到第j站都没有乘客上下车，count[i],...,count[j - 1]无操作；

在第j + 1站下车k人，所以count[j] -= k

为了方便起见，我们缩小问题的规模，以具体的数字代替抽象的代数字母，假如我们就只有3个公交站，取示例中的前2行，

公交车刚开始上的人数是0，vector<int> count(4, 0)；
读取第1行，到达第1站，公交车上10人，说明上车10人，无人下车，count[0]+= 10，到达第2站公交车上依然是10人，说明也无人上车和下车，到达第3站，公交车上0人，说明10人下车，count[2] -= 10；
读取第2行，公交车到达第2站，公交车上20人，说明上车20人无人下车，count[1] += 20，第3站车上20人，说明无人下车，第4站车上0人，说明有20人下车, count[3]-=20。

遍历结束，得到count = {10, 20, -10，-20}，那么最后每个站点的乘客数就很清楚了，到达第1站前车上乘客0人，到达后上车10人，所以第1站发车前车上10人，第2站到站后上车20人，所以第2站发车前车上乘客10 + 20 = 30人，第3站到站后下车10人，所以发车前车上乘客 30 - 10 = 20人。意思搞清楚之后，代码就很好写了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> res(n, 0);
        vector<int> counter(n + 1, 0);
        for (auto &booking : bookings)
        {
            int start = booking[0];
            int end = booking[1];
			// 记录每个booking的开始和结尾即可，中间的站点人数无变化
            counter[start - 1] += booking[2]; // start站上车
            counter[end] -= booking[2]; // end + 1站下车
        }
        res[0] = counter[0];
        for (int i = 1; i < n; i++)
        {
            res[i] = res[i - 1] + counter[i];
        }
        return res;
    }