这道题定为 hard 级别的原因并非是解决思路有多难想, 而是难在了效率的瓶颈.
要求在 O(n) 的复杂度情况下解决. 要知道, 完整的迭代一次就需要 O(n), 这相当于要求在一次迭代过程中, 计算出最大连续序列的长度来.
比较直接的思路是, 先排个序, 然后完整迭代, 中途记录 max 连击. 这个思路非常简单, 但且不论排序, 那一次完整的迭代就几乎要超标.
这种情况下, 以空间换时间就是最佳的选择. 如果我们在迭代过程中, 尝试记录当前最大的连续序列长度呢? 这几乎是矛盾的, 因为原数组并非有序. 如何可以知道连续序列的存在?
这让我想到了生活中一个真实的用例: 整理书籍. 学生时代, 每当大考之后, 都会清理书籍, 入库或者变卖. 我们是如何分类清理的呢? 遇到一本书, 看其属于哪一类, 然后放在一个固定的位置. 当全部书籍翻过一遍之后, 就会很自然的出现一堆堆的书堆. 每一堆都是同一类书籍. 我们很清楚的看到哪一类的书籍最多. 最高的那个就是啦.
这里也是一样, 如果我们弄一个 hash 表(key 为数组值, value 为连续序列 size), 将数组里每一个元素都放入表中, 然后发现连续, 则进行 +1 操作. 具体来说, 就是:
- 若 map[i+1] 和 map[i-1] 存在, 那么 i-1, i, i+1 构成一个三元序列, size == 3;
- 若只有 map[i+1] 或者只有 map[i-1], 那么 size = 2;
- 若 map[i+1] 和 map[i-1] 都不存在, 那么 size = 1; (自己)
上面三种情况可以写成一个式子:
map[i] = map[i-1] + map[i+1] + 1; // 左边记录的序列长度 + 右边记录的序列长度 + 自己
但当 map[i] 的值更新后, 我们还应该将其最新值(长度)扩展至该连续序列的边界上去. 可是如何扩展呢?
如 map[i] 的左边最远的连续节点是谁? 右边的最远连续节点是谁? 显然左边可以递推至 map[i-1] 那去, 右边同理. map[i-1] 如果等于1, 表示到它这就断了, 如果等于2, 那么表示它的左边还有一个连续节点.
那么这个节点的位置也可以用一个式子表示:
map[i - map[i-1]] // 左边最远节点, 用当前位置 - 左边的长度, 正好获得最左连续节点的坐标.
map[i + map[i+1]] // 右边同理.
所以当 map[i] 的值更新后, 应推广至最左与最右. 即:
map[i - map[i-1]] = map[i + map[i+1]] = map[i] = map[i-1] + map[i+1] + 1;
最后, 由于我们只关心最长连续序列的长度, 所以我们设置一个变量来记录它, 如 max.
max = std::max(max, map[i]);
综合上述几个式子, 可以归并为一句话:
max = std::max(max, map[i] = map[i - map[i-1]] = map[i + map[i+1]] = map[i-1] + map[i+1] + 1);
这句话即为核心了.
由于哈希表 unordered_map 默认值为 0. 所以如果遇到一个新值, 则记 map[i] == 1. 如果 map[i] != 0, 显然这个值我们已经存在于 hash 表中, 可以舍弃, 进行下一次迭代.