[LeetCode] 221. Maximal Square

本文主要是介绍[LeetCode] 221. Maximal Square，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题：https://leetcode.com/problems/maximal-square/description/

#题目

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example:

Input:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

思路

方法 1

某一行以前的矩阵，可以找出以该行为底的最大正方形。
具体做法：
tmpVec有相同的列数。
逐行扫描矩阵，
当该行中某元素为 ‘1’，tmpVec对应位的数值加1。否则，tmpVec对应位置为0。
然后将tmpVec视为一系列高为 tmpVec值的矩形图，然后计算最大矩形。可以利用求类似问题的方法（最大矩形，只是最后面积的计算应是 (min(heigh,right-left))^2 ）

补充：

从每行往上看，从每行当起点可以将图视为一个直方图，求每个图中的最大正方形面积。

具体求法，对每列找左右边界，然后取边界长和高的最小值作为正方形的边长。

这里用到了找边界的 dp 方法。
注意:

初始设置：leftLessIndex[0] = -1;rightLessIndex[COL -1 ] = COL;转移方程:int ti = i - 1;  //首先取下一个while(ti!=-1 && heights[ti]>= heights[i]){ //判断是否为 最大边界ti = leftLessIndex[ti];}leftLessIndex[i] = ti;int tj = j + 1;while(tj != COL  && heights[tj]>= heights[j])tj = rightLessIndex[tj];rightLessIndex[j] = tj;

class Solution {public int maximalSquare(char[][] matrix) {int ROW = matrix.length;if(ROW == 0)return 0;int COL = matrix[0].length;int[] heights = new int[COL];int[] leftLessIndex = new int[COL];leftLessIndex[0] = -1;int[] rightLessIndex = new int[COL];rightLessIndex[COL -1 ] = COL;int res = 0;for(char[] tline:matrix){for(int i = 0 ; i < COL ;i++){heights[i] = (tline[i] == '0'? 0:heights[i]+1);}for(int i = 1 ; i < COL ;i++){int j = COL - 1 - i;int ti = i - 1;while(ti!=-1 && heights[ti]>= heights[i]){ti = leftLessIndex[ti];}leftLessIndex[i] = ti;int tj = j + 1;while(tj != COL  && heights[tj]>= heights[j])tj = rightLessIndex[tj];rightLessIndex[j] = tj;}for(int i = 0 ; i< COL ;i++){int len = Math.min(heights[i],rightLessIndex[i] - leftLessIndex[i] -1);res =Math.max(res,len * len);}}return res;}
}

方法2

DP思想，设dp[i][j] 为右下角位置为[i][j] 的正方形的最大的边长。
这里对正方形产生做了巧妙的分析。
一个正方形的增加可以看做是
dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]) + 1
https://leetcode.com/problems/maximal-square/solution/

#code

class Solution:def maximalSquare(self, matrix):""":type matrix: List[List[str]]:rtype: int"""rows = len(matrix)if rows == 0:return 0;cols = len(matrix[0])dp = [[0]*(cols + 1) for i in range(rows + 1)]maxlen = 0;for i in range(1,rows+1):for j in range(1,cols + 1):if matrix[i-1][j-1] == '1':dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j],dp[i][j-1]) ) + 1maxlen = max(maxlen,dp[i][j])return maxlen*maxlen