建站行业分析,长沙网站搜索引擎优化,wap网络,zoho crm题目
在一个由 ‘0 和 ‘1 组成的二维矩阵内#xff0c;找到只包含 ‘1 的最大正方形#xff0c;并返回其面积。
示例 1#xff1a; 输入#xff1a;matrix [[1,0,1,0,0],[1,0, 和 ‘1 组成的二维矩阵内找到只包含 ‘1 的最大正方形并返回其面积。
示例 1 输入matrix [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]
输出4示例 2 输入matrix [[0,1],[1,0]]
输出1示例 3
输入matrix [[0]]
输出0提示
m matrix.lengthn matrix[i].length1 m, n 300matrix[i][j] 为 ‘0 或 ‘1 解答
源代码
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) {for (int j 0; j matrix[0].length; j) {if (matrix[i][j] 1) {if (i 0 || j 0) {dp[i][j] 1;} else {dp[i][j] Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) 1;}}maxSide Math.max(maxSide, dp[i][j]);}}return maxSide * maxSide;}
}
总结
隐隐觉得是动态规划但是不知道怎么根据之前的dp值推算下一个dp值看了题解学习到了新的思路dp[i][j] min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) 1。
