题目描述：找出题目中最大的1正方形。

题目链接：Leetcode 221. Maximal Square

思路：当我们判断以某个点为正方形右下角时最大的正方形时，那它的上方，左方和左上方三个点也一定是某个正方形的右下角，否则该点为右下角的正方形最大就是它自己了。这是定性的判断，那具体的最大正方形边长呢？我们知道，该点为右下角的正方形的最大边长，最多比它的上方，左方和左上方为右下角的正方形的边长多1，最好的情况是是它的上方，左方和左上方为右下角的正方形的大小都一样的，这样加上该点就可以构成一个更大的正方形。 但如果它的上方，左方和左上方为右下角的正方形的大小不一样，合起来就会缺了某个角落，这时候只能取那三个正方形中最小的正方形的边长加1了。假设dpi表示以i,j为右下角的正方形的最大边长，则有
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

代码如下

class Solution:
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0
        m = len(matrix)
        n = len(matrix[0])
        ans = 0
        d = [[0 for i in range(n)] for _ in range(m)]
        for i in range(m):
            if(matrix[i][0]=="1"):
                d[i][0]=1
                ans = 1
        for j in range(n):
            if(matrix[0][j]=="1"):
                d[0][j]=1
                ans = 1
        for x in range(1,m):
            for y in range(1,n):
                if matrix[x][y]=="1":
                    d[x][y] = min(d[x-1][y-1],min(d[x-1][y],d[x][y-1])) + 1
                ans = max(d[x][y],ans)
        return ans * ans
        

或者沿用之前矩形的办法，只不过是限制了长宽要相等。

class Solution:
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0
        m = len(matrix)
        n = len(matrix[0])
        h = [0 for _ in range(n)]
        ans = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j]=="1":
                    h[j]+=1
                else:
                    h[j]=0
            # print(h)
            ans = max(ans,self.getLargest(h))
        return ans
        
        
        
    # 这个办法也可以
     def getLargest(self,heights):
        ans = 0
        s = []
        for i in range(len(heights)+1):
            curr = -1 if i==len(heights) else heights[i]
            while(s and heights[s[-1]] > curr):
                h = heights[s.pop()]
                w = i if not s else (i-s[-1]-1)
                l = min(h,w)
                ans = max(ans,l*l)
            s.append(i)
        return ans
          
    def getLargest(self,heights):
        ans = 0
        for i in range(len(heights)):
            l = i - 1
            r = i + 1
            while(l>=0 and heights[i] <= heights[l] and (r-l-1)<heights[i]):
                l -= 1
            while(r<len(heights) and heights[i] <= heights[r] and (r-l-1)<heights[i]):
                r += 1
            width = min((r-l-1),heights[i])
            ans = max(width*width,ans)
        return ans
        
        

参考链接

• [LeetCode] Maximal Square 最大正方形