LeetCode 解題紀錄 221. Maximal Square 圖片中最大的正方形
繼 200. Number of Islands 後，又遇到一個影像處理的問題。 這題要用動態規劃來解，菜雞如我第一時間沒想到動態規劃， 但是後來也自己解出來了，紀錄一下我的解題心路歷程。 題目簡介： 給你一張尺寸為 m x n 像素且只包含（0,1）的圖片稱為 Matrix ， 其中 1 代表有像素的區域，找出此張圖片中含有 1 的最大正方形區域面積。 第一階段想法：循序檢測法 把每個點都當作候選正方形的左上角， 先求 Row 再驗證每個 Col 是否符合正方形區域預想？ 若有，就回傳正方形區域面積； 若無，就回傳 0。 假設圖片中有 N 個元素，這個想法的時間複雜度為： $$O(N^{2})$$ 但是我們會遇到一個特殊情況，當最大正方形在驗證失敗的候選正方形的的情況， 像是： 就很尷尬，其中 $$S_m$$ 不等於 6 的原因是本圖中最大正方形是交由 min(m, n) 決定， 所以不用檢查到 $$S_m = 6$$ 可以降低計算時間。 結果： Wrong Answer 第二階段：動態規劃法 所以我決定再不增加時間複雜度的情形下，由小到大、每個正方形都檢測。 使用動態規劃，每一步驟又拆成兩小步： 第一步：驗證對角線是否為 '1' ？ 第二步：驗證相應 X, Y軸是否為 '1' ？ 若有任一步檢測到 '0' ，則回傳步數 S 的平方當作正方形面積。 不過鑑於這個作法時間複雜度遇到 Worst Case （全為 '1' 的圖片時）仍為 $$O(N^{2})$$ 結果： Time Limited Error 第三階段：利用影像（數據）特性降低時間複雜度。 問自己一個問題： 最低滿足圖片中最大正方形的條件是什麼？ 答案是任何大於（長/2）*（寬/2）的正方形， 因為本題目中不考慮重疊問題，所以用數學上來說： 一圖片尺寸為 m*n ，若有任意正方形面積大於（m/2 + k）（n/2 + k）， 而 k 恆大於零的話，此正方形為圖片中最大的正方形就成立。 而候選次大正方形面積必定為（m/2 - k）（n/2 - k）， 所以每個點出發後， 檢測 (m*n/4) + m + n - 1 個像素就知道這個正方形是不是最大的了。 結果： Accept