这道题有两个思路， 一是沿用085的maximum rectangle的思路， 稍作改进即可， 代码如下， 这个方法运行192ms

class Solution:    # @param {character[][]} matrix    # @return {integer}    def maximalSquare(self, matrix):        ans = 0        for i in range(0,len(matrix)):            for j in range(0, len(matrix[0])):                if i == 0:                    matrix[i][j] = int(matrix[i][j])                else:                    if matrix[i][j] == "0":                        matrix[i][j] = 0                    else:                        matrix[i][j] = matrix[i-1][j] + 1        for m in matrix:            ans = max(ans, self.largestRectangleArea(m))        return ans    def largestRectangleArea(self, height):        ans = 0        s = []        for i in range(0, len(height)):            left = i            while (s != []) and (s[-1][0] > height[i]):                left = s[-1][1]                l = min(i - left, s[-1][0])                ans = max(ans, l * l)                s.pop()            s.append([height[i], left])        right = len(height)        while s != []:            left = s[-1][1]            l = min(right - left, s[-1][0])            ans = max(ans, l * l)            s.pop()        return ans

看到tag中有 dp, 试着用dp 做了一个 运行时间是200ms， 看出在复杂度都是O(n*n)的情况下 时间区别不大 代码如下

class Solution:    # @param {character[][]} matrix    # @return {integer}    def maximalSquare(self, matrix):        ans = 0        m = len(matrix)        if m == 0:            return 0        n = len(matrix[0])        dp = [[0] * n for i in range(0,m)]        for i in range(0,m):            for j in range(0,n):                dp[i][j] = int(matrix[i][j])                if i and j and dp[i][j]:                    dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])                    ans = max(ans, dp[i][j] * dp[i][j])        return ans