Amazon OA2 面经

叫我戴德兰 发表于 2018-12-7 13:08
无法优化到O(1)吧，至少需要一个array来存。

讲错了，是怎么优化到O[n]的空间复杂度

ZihaoZhai 发表于 2018-12-7 13:36
讲错了，是怎么优化到O[n]的空间复杂度

因为你只需要matrix的上一行，之前的留着你也不用。你可以就用matrix的一行一直更新就是了。

叫我戴德兰 发表于 2018-12-12 02:31
因为你只需要matrix的上一行，之前的留着你也不用。你可以就用matrix的一行一直更新就是了。

好的，谢谢

第一题是substring，不是maximal substring，当然不能sliding window啊。