给定一个方阵,每个单元pixel either black or white. 找出四条边都是black pixels的最大sub-matrix
Naive: O(N^4)
先找N by N, 如果判断成功结束。失败的话,1尝试第二大的 N-1 * N-1。iterate所有这个size的。。逐渐尝试
Better: O(N^3)
上面的解法之所以慢是因为每检查一个可能符合要求的方阵,要O(N)的工作量。 所以可以预先做一下处理。把isSquare的复杂度降为O(1)
这题的技巧就是Pre-Processing。
变形题:


这题是一个搜索类题目。
这个解法好有趣

DFS
