【LeetCode】【算法】221. 最大正方形

LeetCode 221. 最大正方形

题目描述

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

思路

思路：动态规划。初始化时，第0列和第0行，若nums[i][j]=1则dp[i][j]初始化为1，否则初始化为0。规划方程：
dp[i][j]=Math.min(Math.min(nums[i-1][j], nums[i-1][j-1]), nums[i][j-1])+1
再用一个maxSide变量来存储最大正方形边长，在求解dp数组过程中不断更新maxSide变量的值

代码

class Solution {public int maximalSquare(char[][] matrix) {// 动态数组初始化int maxSide = 0;int[][] dp = new int[matrix.length][matrix[0].length];for (int i = 0; i < matrix.length; i++){if (matrix[i][0] != '0') {dp[i][0] = 1;maxSide = 1;}}for (int j = 0; j < matrix[0].length; j++){if (matrix[0][j] != '0') {dp[0][j] = 1;maxSide = 1;}}for (int i = 1; i < matrix.length; i++) {for (int j = 1; j < matrix[0].length; j++) {if (matrix[i][j] == '1'){dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;}maxSide = Math.max(maxSide, dp[i][j]);}}return maxSide * maxSide;}
}