前几天面试了字节跳动，记录下面试遇到的算法题

输入： 用户日志(time, user_id, login | logout)
输出：同时在线人数的峰值，精确到秒

一开始，想了一分钟左右，想到了一个比较简单粗暴的方式。

使用位图的思想，将一天 分成 86400 秒，每秒单独统计，最后遍历一遍，找最大的值所对应的秒数

总的来说简单粗暴，也是比较容易想到的方式。只是由于按照每秒来统计了，所以写入到这个位图的效率是很低的。如果用户一天都在线， 那么就要写86400 次，明显是很慢的。

面试官一看这么粗暴，问了句，有没有优化的方案？

按照套路来，要么动态规划把历史记录一下，要么二分一下。动态规划明显不适用，二分的思想好像是可行的。

先将一天分成24小时，按照上面的方法统计一遍，找到峰值的小时，然后从这小时里面按照分钟统计一遍，找到峰值的分钟，再将分钟分成60秒，再统计一遍

理论上，每个用户跨越的时间越长，这样统计起来应该是会比第一种方式优秀很多。

但是面试官的问题来了，如果有多个峰值怎么办，最坏情况下每秒都是峰值，这种方式会比第一种方式慢得多

那就得继续想呗，想了几分钟，面试官看我想不出来就放弃了，我的心也凉了下，感觉没戏了

面试结束之后，继续想了下这个问题有没有更好的解法

毕竟同一个坑不能栽进去两次对不对。

可能是最优解的解法来了

跳开之前的统计所有秒数的想法，这个问题的解法就简单多了

我们先来想一下什么时候会有峰值，肯定是在线人数最多的时候。那么某个时间点在线的人数怎么算呢，很明显是 所有在这个时间点之前登入的 - 在这个时间点之前所有登出的。

那么算法也很简单，

1. 定义三个变量，其中一个记录当前在线人数（currentVal）,一个最大值（maxVal），最后一个记录其对应的秒数的数组(seconds)。
2. 将日志分成 登录，登出 两种状态，并且根据时间进行正向排序
3. 遍历步骤2得到的日志，如果是登录则 currentVal + 1 并且跟 maxVal 对比，如果比 maxVal 大，则将 maxVal 设置为 currentVal, seconds 设置为 当前秒数， 如果 maxVal == currentVal, 则 seconds 增加当前秒数。如果是登出，则 currentVal - 1 （不过更完美点应该判断下当前是不是maxVal, 如果是则将上一次峰值的秒数，到当前秒数的区间写入到 seconds）
4. 遍历完成之后得到的 maxVal 就是 峰值， seconds 就是对应的秒数列表

比如说，日志长这样

uid        登录时间         登出时间
uid1       00:00:01        00:00:10
uid2       00:00:02        00:00:05
uid3       00:00:03        00:00:05

步骤2中，将其变成

uid     action      时间     
uid1    登入     00:00:01    
uid2    登入     00:00:02
uid3    登入     00:00:03    
uid2    登出     00:00:05  // 到这里的时候需要 将上一次峰值到当前值（00:00:03 到 00:00:04 ）写入到 seconds
uid3    登出     00:00:05
uid1    登出     00:00:10

`currentVal` -> 1   -> 2   -> 3   -> 2   -> 1   -> 0
`maxVal`     -> 1   -> 2   -> 3   -> 3   -> 3   -> 3
`seconds`    -> [1] -> [2] -> [3] -> [3,4] -> [3,4] -> [3,4] 

最后，好像虽然做不出来，面试还是过了，感谢面试官抬一手。 如果有更好的解法，或者这个解法有问题，也方便留言。