Leetcode題解 Python & C#：四月挑戰DAY27 Maximal Square

給一個2D矩陣，其中只有 1 或 0 ，找出最大的連續 1 組成的最大正方形面積。

首先來想要怎樣去找任意一個正方形的面積。

如果選定某一位置，那正方形會在往右下延伸、或左上，簡單來說就是四周。

不過這樣相當不容易寫，而且也會效率不佳。

再觀察一下，正方形出現時會有怎樣的情形？

假設有個面積為 4 的正方形：

基礎假設

可以發現組成邊長2的正方形，其相鄰加身自身會有2個連續出現1超過二次。

同理邊長為3的正方形。

計算流程

於是各欄只要計數1的連續出現次數，接下來問題變成要如何從數列中找出最大的正方形面積。

接著要去從數列中求出最大的正方形面積。

我這裡使用暴力破解法，以自身為左右索引的起始點，往左右找有大於自身數值的個數。
如 2 ，只要往左右再找一個，因為自身本身可以當作一個計數。

過程中，數值小於當前的最大面積的邊長也可以跳過不往左右找。


Python

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]: return 0       
        rows,cols= len(matrix), len(matrix[0])
        cur = [0]*cols
        maxSideLength = 0
        for y in range(rows):
            # 逐行掃瞄
            for x in range(cols):
                if matrix[y][x] == "1":
                    cur[x] += 1
                else:
                    cur[x] = 0
            # 檢查連續最大值
            for x in range(cols):                 
                v = cur[x]
                if v <= maxSideLength: continue                    
                v -= 1
                l, r = x, x
                while v:
                    if l > 0 and cur[l-1] >= cur[x]:
                        l-=1
                        v-=1
                        continue
                    if r < cols-1 and cur[r+1] >= cur[x]:
                        r+=1
                        v-=1
                        continue
                    break
                if v==0: 
                    maxSideLength = max(maxSideLength, cur[x])
        return maxSideLength**2

C#

public class Solution {
    public int MaximalSquare(char[][] matrix) {
        if(matrix.Length == 0 || matrix[0].Length == 0){return 0;}
        var cur = new int[matrix[0].Length];
        Array.Fill(cur, 0);
        int maxSideLength = 0;
        
        for(int y = 0; y < matrix.Length; y++)
        {
            for(int x = 0; x < matrix[0].Length; x++)
            {
                if(matrix[y][x]=='1')
                {
                    cur[x] += 1; 
                }
                else
                {
                    cur[x] = 0;
                }               
            }

            for(int x = 0; x < matrix[0].Length; x++)
            {
                if(cur[x] <= maxSideLength)
                {
                    continue;
                }
                int num = cur[x]-1;
                int l = x; int r = x;
                while(num > 0)
                {
                    if(l > 0 && cur[l-1] >= cur[x])
                    {
                        l -= 1;
                        num -= 1;
                        continue;
                    }
                    if(r < matrix[0].Length-1 && cur[r+1] >= cur[x])
                    {
                        r += 1;
                        num -= 1;
                        continue;
                    }
                    break;
                }
                if(num==0)
                {                    
                    maxSideLength = cur[x];
                }
            }
        }
        
        return maxSideLength*maxSideLength;
    }
}