在一個由 0 和 1 組成的二維矩陣內，找到只包含 1 的最大正方形，并返回其面積。

示例:

輸入:?

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

輸出: 4

思路：和最大長方形類似（可以參照https://mp.csdn.net/postedit/102420219，不過每次的max換位長和寬中選取最小值，算他們的平方）

提交的代碼：

class Solution {
? ? public int maximalSquare(char[][] matrix) {
? ? ? ? int n = matrix.length;
? ? ? ? int m=0;
? ? ? ? if(n>0)
? ? ? ? {
? ? ? ? ? ? ?m = matrix[0].length;
? ? ? ? }
? ? ? ? if(m==0&&n==0)
? ? ? ? {
? ? ? ? ? ? return 0;
? ? ? ? }
?? ??? ?int i,j,max=-1,t=0,k;
?? ??? ?int[][] dp1 = new int[n][m];
?? ??? ?for(i=0;i<n;i++)
?? ??? ?{
?? ??? ??? ?for(j=0;j<m;j++)
?? ??? ??? ?{
?? ??? ??? ??? ?if(matrix[0][0]=='1')
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?dp1[0][0]=1;
?? ??? ??? ??? ?}
?? ??? ??? ??? ?else if(matrix[0][0]=='0')
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?dp1[0][0]=0;
?? ??? ??? ??? ?}
?? ??? ??? ??? ?if(i==0&&j>0)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?if(matrix[i][j]=='1')
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?dp1[i][j] = dp1[i][j-1]+1;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?else
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?dp1[i][j] = 0;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ??? ?else if(j==0&&i>0)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?if(matrix[i][j]=='1')
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?dp1[i][j]=1;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ??? ?else if(i>0&&j>0)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?if(matrix[i][j]=='1')
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?dp1[i][j] = dp1[i][j-1]+1;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?else
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?dp1[i][j] = 0;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ??? ?t = dp1[i][j];
?? ??? ??? ??? ?for(k=i;k>=0;k--)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?t = java.lang.Math.min(dp1[k][j], t);
?? ??? ??? ??? ??? ?if(java.lang.Math.min(t,(i-k+1))*java.lang.Math.min(t,(i-k+1))>max)
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?max = java.lang.Math.min(t,(i-k+1))*java.lang.Math.min(t,(i-k+1));
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ?}
?? ??? ?return max;
? ? }
}

完整的代碼：

public class Solution85 {
?? ?public static int maximalRectangle(char[][] matrix) {
?? ??? ?int n = matrix.length;
? ? ? ? int m=0;
? ? ? ? if(n>0)
? ? ? ? {
? ? ? ? ? ? ?m = matrix[0].length;
? ? ? ? }
? ? ? ? if(m==0&&n==0)
? ? ? ? {
? ? ? ? ? ? return 0;
? ? ? ? }
?? ??? ?int i,j,max=-1,t=0,k;
?? ??? ?int[][] dp1 = new int[n][m];
?? ??? ?for(i=0;i<n;i++)
?? ??? ?{
?? ??? ??? ?for(j=0;j<m;j++)
?? ??? ??? ?{
?? ??? ??? ??? ?if(matrix[0][0]=='1')
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?dp1[0][0]=1;
?? ??? ??? ??? ?}
?? ??? ??? ??? ?else if(matrix[0][0]=='0')
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?dp1[0][0]=0;
?? ??? ??? ??? ?}
?? ??? ??? ??? ?if(i==0&&j>0)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?if(matrix[i][j]=='1')
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?dp1[i][j] = dp1[i][j-1]+1;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?else
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?dp1[i][j] = 0;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ??? ?else if(j==0&&i>0)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?if(matrix[i][j]=='1')
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?dp1[i][j]=1;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ??? ?else if(i>0&&j>0)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?if(matrix[i][j]=='1')
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?dp1[i][j] = dp1[i][j-1]+1;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?else
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?dp1[i][j] = 0;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ??? ?t = dp1[i][j];
?? ??? ??? ??? ?for(k=i;k>=0;k--)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?t = java.lang.Math.min(dp1[k][j], t);
?? ??? ??? ??? ??? ?if(t*(i-k+1)>max)
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?max = t*(i-k+1);
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ?}
?? ??? ?return max;
? ? }
?? ?public static void main(String[] args)
?? ?{
?? ??? ?char[][] a = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
?? ??? ?System.out.println(maximalRectangle(a));
?? ?}
}
?

總結

以上是生活随笔為你收集整理的Leetcode--221.最大正方形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。