10 张图解字节面试题，大厂要求的确高

发表于 2年以前 | 总阅读数：349 次

大家好，今天讲解一道流传较为广泛的字节算法面试题，给定用户登录以及登出的日志，计算最大在线峰值人数。

"id" : 1, "login":2019-07-25 02:00:00, "logout" : 2019-07-25 04:00:00
"id" : 10, "login":2019-07-25 06:00:00, "logout" : 2019-07-25 08:00:00
"id" : 12, "login":2019-07-25 07:00:00, "logout" : 2019-07-25 08:00:00
...

想一想该怎样解决这个问题。

这个问题本质是这样的：

其中横轴是时间，纵轴是id，其中每一条横线表示此人的在线时间，我们需要计算在横轴上以1秒为间隔，[1s-2s]，[2s-3s]，[3s-4s]等等，看有多少人落在这些间隔中，然后从中取出一个最大值。

可是该怎样计算呢？

很简单，我们可以把一天用一个数组表示，数组大小为24*60*60，即arr[86400]表示一天中的所有秒数，然后把“2019-07-25 07:00:00”这样的时间表示转为Unix时间，转换后为1564009200，可以看到这是一个整数，上述示例中的时间转换后就为：

"id" : 1, "login":1563991200, "logout" : 1563998400
"id" : 10, "login":1564005600, "logout" : 1564012800
"id" : 12, "login":1564009200, "logout" : 1564012800

怎么样，这就好看多了吧，然后呢？

然后我们把这些数据减去“2019-07-25 00:00:00”，表示这是这一天的第几秒，“2019-07-25 00:00:00”转为Unix时间后为1563984000，然后再讲上述日志减去该时间得到：

"id" : 1, "login":7200, "logout" : 14400
"id" : 10, "login":21600, "logout" : 28800
"id" : 12, "login":25200, "logout" : 28800

现在就更清晰了吧，其中第一条表示数组从arr[7200]到arr[14000]都加1，表示此人在这个时间段内在线，其它同理，这样在最后我们扫描一遍arr然后取出一个最大值就是在线峰值人数，就像这样：

有的同学可能觉得到这里已经给出了问题的答案，然而这并不是问题的最终答案，还可以进一步优化。

实际上该问题和LeetCode上一个题目完全一样，LeetCode的题目是这样问的：给定n架航班，以及k个预定信息bookings，每个预定信息i为bookings[i] = [firsti, lasti, seatsi]，表示从航班firsti到航班lasti预定seatsi个作为，问最后每架航班最后预定了多少座位，示例：

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

航班:        1   2   3   4   5
预定1:       10  10
预定2:           20  20
预定3:           25  25  25  25

结果:        10  55  45  25  25

怎么样，是不是这两个题目完全一样，如果按照之前分析的思路的话代码就可以这样写以下为C++代码：

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    vector<int> res(n, 0);
    for (auto& v: bookings) {
        for (int i = v[0] - 1; i < v[1];i++) {
            res[i] += v[2];
        }
    }
    return res;
}

代码非常简单，然后该代码是非常低效的，其低效的根本原因在于对于每一个给定的预定信息我们需要根据其范围更新数组的值，给定预定信息[2,10,N]，我们需要用for循环去更新res[2]到res[10]之间的所有元素、给定预定信息是[2,1000,N]，那么我们就需要用for循环去更新res[2]到res[1000]之间所有的元素，但这有必要的吗？

实际上这并不是必须的，举个例子你就明白了，假设有一个的数组，我们把该数组的第2到第7之间的元素设置为10，那么最简单的方法是这样的：

但我们其实没有必要设置6次，我们只需要设置两次即可：

这是什么意思呢？熟悉“累加和”概念的同学应该比较熟悉，所谓累加和就是给定数组arr，对每一个元素arr[i]计算：

arr[i] += arr[i-1]

也就是当前元素的值加上前一个元素的值的得到的就是从数组开头到当前位置i的和是多少，如果我们对这张图应用累积和：

得到的就是：

现在你应该明白了吧。

实际上不管这个范围有多大，我们也只需要设置两次即可：把开头设置为10，把末尾的下一个元素设置为-10，这极大加快了计算速度。

假设现在又来了一个新的预定信息，把下标从2到3的数组元素设置为15，那么应用刚才的原则，我们可以把下标2以及下标4的值分别设置为15和-15：

接着我们计算这两部分的和：

最后对该结果计算累积和，得到：

你会发现这和第一种方法直接将这部分的和累加的结果是一样的：

是不是很神奇！

好啦，有了这些分析代码就非常简单了：

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    vector<int> res(n, 0);
    for (auto& v: bookings) {
        res[v[0] - 1] += v[2];
        if (v[1] < n) res[v[1]] += -v[2];
    }
    for (int i = 1; i < n; i++)
        res[i] += res[i-1];
    return res;
}

这段代码效率非常高，时间复杂度只有O(N)。

最终该方法可以直接应用在计算峰值在线人数，不同的是最后我们从数组res中返回一个最大值就可以了。

怎么样，这是不是很有趣的一个面试题。