前言
最近被我大哥安利了一道算法题, 这道题说难, 还不至于我做不出来, 说简单吧, 我还想不到最优解, 等把最优解告诉我之后, 我还正好能理解....一眼就看到了函数里的六层循环, 么的说, O(n^6).
这时, 我大哥说他的时间复杂度是 O(n^3). 那我这小心情, 必须整出来, 再想.
方案二
上面的六层循环中, 能不能想办法去掉一层呢?...在最后判断是否全1的循环中, 如果左上的数字是0, 那必然没有全1子矩阵了
再如果向下找的时候, 碰到0, 那下一列的时候也没必要超过这里了, 因为子矩阵至少有一个0了, 如下图:
?...上面的四层循环, 有没有什么办法能再减少一层呢?
想一下, 我们在第四层循环中, 向右遍历, 找的是什么?...是连续1的个数, 如果我们不用向右遍历, 直接就知道了这个连续1的个数, 那是不是就可以把这一层也省了呢?
那么问题来了, 如何不遍历就知道呢? 预处理.
