做挂广告网站,沈阳建筑大学网络信息化中心,现在还做响应式网站吗,网站建设的技术目标在一个由 0 和 1 组成的二维矩阵内#xff0c;找到只包含 1 的最大正方形#xff0c;并返回其面积。
示例:
输入:
1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
输出: 4
思路#xff1a;和最大长方形类似#xff08;可以参照https://mp.csdn.net/postedit/102420219找到只包含 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 m0; if(n0) { m matrix[0].length; } if(m0n0) { return 0; } int i,j,max-1,t0,k; int[][] dp1 new int[n][m]; for(i0;in;i) { for(j0;jm;j) { if(matrix[0][0]1) { dp1[0][0]1; } else if(matrix[0][0]0) { dp1[0][0]0; } if(i0j0) { if(matrix[i][j]1) { dp1[i][j] dp1[i][j-1]1; } else { dp1[i][j] 0; } } else if(j0i0) { if(matrix[i][j]1) { dp1[i][j]1; } } else if(i0j0) { if(matrix[i][j]1) { dp1[i][j] dp1[i][j-1]1; } else { dp1[i][j] 0; } } t dp1[i][j]; for(ki;k0;k--) { t java.lang.Math.min(dp1[k][j], t); if(java.lang.Math.min(t,(i-k1))*java.lang.Math.min(t,(i-k1))max) { max java.lang.Math.min(t,(i-k1))*java.lang.Math.min(t,(i-k1)); } } } } return max; } }
完整的代码 public class Solution85 { public static int maximalRectangle(char[][] matrix) { int n matrix.length; int m0; if(n0) { m matrix[0].length; } if(m0n0) { return 0; } int i,j,max-1,t0,k; int[][] dp1 new int[n][m]; for(i0;in;i) { for(j0;jm;j) { if(matrix[0][0]1) { dp1[0][0]1; } else if(matrix[0][0]0) { dp1[0][0]0; } if(i0j0) { if(matrix[i][j]1) { dp1[i][j] dp1[i][j-1]1; } else { dp1[i][j] 0; } } else if(j0i0) { if(matrix[i][j]1) { dp1[i][j]1; } } else if(i0j0) { if(matrix[i][j]1) { dp1[i][j] dp1[i][j-1]1; } else { dp1[i][j] 0; } } t dp1[i][j]; for(ki;k0;k--) { t java.lang.Math.min(dp1[k][j], t); if(t*(i-k1)max) { max t*(i-k1); } } } } 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)); } }
