广州做贷款有什么网站,手机怎么做微信公众号,2022年一建考试最新消息,网站赏析案例文章目录题目描述思路 代码更新版题目描述
显而易见地可以用dp来写#xff0c;问题在于如何考虑状态转移方程
思路 代码
首先再加一层外墙#xff0c;就不用边界判断了maxSqure[i]#xff1a;以当前格子为右下角的正方形#xff0c;可达到的最大边长这是由…
文章目录题目描述思路 代码更新版题目描述
显而易见地可以用dp来写问题在于如何考虑状态转移方程
思路 代码
首先再加一层外墙就不用边界判断了maxSqure[i]以当前格子为右下角的正方形可达到的最大边长这是由左、上、左上三个格子的maxSqure来决定的类似木桶短板借用一下leetcode题解中 lzhlyle 大佬的图这个0限制我没太理解这里说说我的理解吧 三个图分别代表全部可能的三种情况左上小了、上小了、左小了 对于这三种情况我们发现采取的值都遵循这个规律直接取三者中最小的值即可 由此可以得到状态转移方程见代码
class Solution {public int maximalSquare(char[][] matrix) {int m matrix.length;int n matrix[0].length;int maxSide 0;// maxSqure[i][j]以当前块为右下角可构造成的最大正方形的边长// 默认给上、左加上一层初始化的0int[][] maxSqure new int[m 1][n 1];for(int i 1; i m; i){for(int j 1; j n; j){if(matrix[i-1][j-1] 1){// 思考可以分成上、左、左上三个格子分别为短板的情况然后此时如何取得min值来得出“三者取最小”的情况maxSqure[i][j]Math.min(Math.min(maxSqure[i-1][j-1],maxSqure[i-1][j]),maxSqure[i][j-1]) 1;maxSide Math.max(maxSqure[i][j], maxSide);}}}return maxSide * maxSide;}
}时间复杂度 O(m * n)空间复杂度 O(m * n)
更新版
class Solution {public int maximalSquare(char[][] matrix) {int[][] maxSquareSize new int[matrix.length 1][matrix[0].length 1];int resSize 0;for(int i 1; i matrix.length; i) {for(int j 1; j matrix[0].length; j) {if(matrix[i - 1][j - 1] 1) {maxSquareSize[i][j] Math.min(maxSquareSize[i - 1][j], maxSquareSize[i][j - 1]);maxSquareSize[i][j] Math.min(maxSquareSize[i][j], maxSquareSize[i - 1][j - 1]);resSize Math.max(resSize, maxSquareSize[i][j]);}}}return resSize * resSize;}
}
