221. 最大正方形

题目描述 在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。 示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 输出: 4 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/maximal-square著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 题目要求找到矩阵matrix中只包含1的最大正方形,并返回其面积。我们可以转换成求子方阵中1的数量。如果子方阵中所有元素的和与子方阵的size的平方相等,那么这个方阵中的元素肯定都是1。 如果采用暴力的解法: 枚举每个起始位置时间复杂度O(n^2); 在该位置下枚举子方阵的大小时间复杂度O(n); 最后需要统计该方阵有多少个1,时间复杂度为O(n^2)。 那么整体来看,使用暴力法的时间复杂度为O(n^5)。这么高的复杂度,肯定是通不过的。但是我们可以利用预计算,提前求出从左上角(0, 0)到任意位置的矩阵中1的数量。再通过简单的加减法,就能求得任意子方阵中1的数量: 图1描述了对于矩阵matrix,通过预计算求得从(0, 0)到任意位置(row, col)的和。我们先忽略sum这个矩阵是怎么求得的,下面我们用它实现O(1)的时间复杂度来计算任意子方阵中1的数量。 图1中红色区域是我们想要求得的解,红色 = 橙色 – 蓝色 – 绿色 + 紫色。因为从左上角到任意位置的和都通过预计算求过了,只需要带入公式用O(1)的时间复杂度就能求得起始位置为(row, col),大小为size的方阵的和。对于整个问题,我们只需要枚举起始位置和枚举方阵的大小,整体的时间复杂度为O(n^3)。 上面的那个例子可以用公式可以表述为:…

Read more