文章目錄

• 題目描述
• 思路 & 代碼
• • • 更新版

題目描述

• 顯而易見地可以用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;} }

總結

以上是生活随笔為你收集整理的【LeetCode笔记】221. 最大正方形（Java、动态规划、思路题）的全部內容，希望文章能夠幫你解決所遇到的問題。

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