摘要:但如果它的上方,左方和左上方為右下角的正方形的大小不一樣,合起來就會缺了某個角落,這時候只能取那三個正方形中最小的正方形的邊長加了。假設表示以為右下角的正方形的最大邊長,則有當然,如果這個點在原矩陣中本身就是的話,那肯定就是了。
Maximal Square
動態規劃 復雜度Given a 2D binary matrix filled with 0"s and 1"s, find the largest square containing all 1"s and return its area.
For example, given the following matrix:
1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0Return 4.
時間 O(MN) 空間 O(MN)
思路當我們判斷以某個點為正方形右下角時最大的正方形時,那它的上方,左方和左上方三個點也一定是某個正方形的右下角,否則該點為右下角的正方形最大就是它自己了。這是定性的判斷,那具體的最大正方形邊長呢?我們知道,該點為右下角的正方形的最大邊長,最多比它的上方,左方和左上方為右下角的正方形的邊長多1,最好的情況是是它的上方,左方和左上方為右下角的正方形的大小都一樣的,這樣加上該點就可以構成一個更大的正方形。但如果它的上方,左方和左上方為右下角的正方形的大小不一樣,合起來就會缺了某個角落,這時候只能取那三個正方形中最小的正方形的邊長加1了。假設dpi表示以i,j為右下角的正方形的最大邊長,則有
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
當然,如果這個點在原矩陣中本身就是0的話,那dpi肯定就是0了。
代碼public class Solution { public int maximalSquare(char[][] matrix) { if(matrix.length == 0) return 0; int m = matrix.length, n = matrix[0].length; int max = 0; int[][] dp = new int[m][n]; // 第一列賦值 for(int i = 0; i < m; i++){ dp[i][0] = matrix[i][0] - "0"; max = Math.max(max, dp[i][0]); } // 第一行賦值 for(int i = 0; i < n; i++){ dp[0][i] = matrix[0][i] - "0"; max = Math.max(max, dp[0][i]); } // 遞推 for(int i = 1; i < m; i++){ for(int j = 1; j < n; j++){ dp[i][j] = matrix[i][j] == "1" ? Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1 : 0; max = Math.max(max, dp[i][j]); } } return max * max; } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/64496.html
摘要:類似這種需要遍歷矩陣或數組來判斷,或者計算最優解最短步數,最大距離,的題目,都可以使用遞歸。 Problem Given a 2D binary matrix filled with 0s and 1s, find the largest square containing all 1s and return its area. Example For example, given t...
摘要:題目要求輸入一個二維數組,其中代表一個小正方形,求找到數組中最大的矩形面積。思路一用二維數組存儲臨時值的一個思路就是通過存儲換效率。從而省去了許多重復遍歷,提高效率。這里我使用兩個二維數組來分別記錄到為止的最大長度和最大高度。 題目要求 Given a 2D binary matrix filled with 0s and 1s, find the largest rectangle ...
摘要:以此類推,如果一直到棧為空時,說明剛出來的豎條之前的所有豎條都比它自己高,不然不可能棧為空,那我們以左邊全部的寬度作為長方形的寬度。 Largest Rectangle in Histogram Given n non-negative integers representing the histograms bar height where the width of each bar...
摘要:題目解答第一眼看這道題以為是個搜索問題,所以用解了一下發現邊界并沒有辦法很好地限定成一個,所以就放棄了這個解法。 題目:Given a 2D binary matrix filled with 0s and 1s, find the largest square containing all 1s and return its area. For example, given the ...
摘要:題目解答這題思路很重要,一定要理清和的參數之間的關系,那么就事半功倍了。表示從左往右到,出現連續的的第一個座標,表示從右往左到出現連續的的最后一個座標,表示從上到下的高度。見上述例子,保證了前面的數組是正方形且沒有的最小矩形, 題目:Given a 2D binary matrix filled with 0s and 1s, find the largest rectangle co...
閱讀 1864·2021-11-25 09:43
閱讀 2146·2021-11-19 09:40
閱讀 3422·2021-11-18 13:12
閱讀 1739·2021-09-29 09:35
閱讀 661·2021-08-24 10:00
閱讀 2505·2019-08-30 15:55
閱讀 1709·2019-08-30 12:56
閱讀 1815·2019-08-28 17:59