[LeetCode] 221. Maximal Square

轉自LeetCode

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

<Solution>

想法如下

• 目標是要找出面積最大的正方形，檢查方式是當目前的位置是 1 時，往對角線右下的方向移動一格，然後檢查該列和該行，到剛剛移動前的行和列，路途中間有沒有都是 1，是的話就是一個正方形。繼續往對角線右下方前進，直到不滿足正方形的條件，並記錄該正方形的邊長

• 上面這點的概念，可以用下列公式來找到每個正方形的邊長

        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

• 所以這題是可以用 dp 的方式來解的，過程當中並紀錄最長邊長即可找到答案

code 如下

Java(參考解答)


kotlin