前往
大廳
主題

LeetCode - 221. Maximal Square 解題心得

Not In My Back Yard | 2022-06-07 12:00:01 | 巴幣 0 | 人氣 197

題目連結:


題目意譯:
給定一個 m × n 填滿著 '0' 和 '1' 的二元矩陣 matrix,找到其中最大的、只包含 1 的方形區域並回傳其面積。

限制:
m == matrix.length
n == matrix[i].length
1 ≦ m, n ≦ 300
matrix[i][j] 只會是 '0' 或是 '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


解題思維:
(這邊假設 matrix 的行列索引值皆從 1 開始。但是大部分程式語言則是從 0 開始,這點需注意)
定義一個二維陣列 D[i][j],其代表著以 matrix[i][j]為右下角的最大正方形之大小。而從下圖中
可以看到當我們已經知道 D[i - 1][j - 1] 、 D[i - 1][j] 和 D[i][j - 1](上圖中以三個紅色框起即為以它們為右下角的最大方形,此例中三者大小依序為 5 、 1 、 3)時。此時我們可以推得 D[i][j](此例中應為 2,其以藍色方形表示)。

因此 D[i][j] 之值即為
min(D[i - 1][j - 1], D[i - 1][j], D[i][j - 1]) + 1
當然,前提是 matrix[i][j] = '1'(才能作為方形的右下角)。如果 matrix[i][j] = '0',則 D[i][j] = 0。

可以看到邊界條件為
對於 i = 0 時,D[0][j] = 0;
對於 j = 0 時,D[i][0] = 0。

因此就像所有動態規劃(Dynamic Programming)的題型,本題中我們從 i = 1、j = 1 開始,由上至下(i 漸增)、由左至右(j 漸增)地依序求出每個位置的值。而當中的最大值即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作