221. Maximal Square（Medium)

这道题剑指offer上也有，比较巧妙，暴力方法需要O(n*k)，而双向队列缩短到了O（n）

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

Example:
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4

不得不说这道题非常巧妙,把每个矩形的问题转换成了二维数组每个数与其正上、正左、左上三个坐标之间的关系，dp(i,j)表示点(i,j)为终点的最大正方形。转移方程式如下：

dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1.

image.png

    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix or not matrix[0]:
            return 0
        row = len(matrix)
        column = len(matrix[0])
        Max = 0
        dp = [[0 for j in range(column)] for i in range(row)]
        for i in range(0, row):
            for j in range(0, column):
                if i == 0 or j == 0:
                    dp[i][j] = int(matrix[i][j])
                elif matrix[i][j] == '1':
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1
                else:
                    dp[i][j] = 0
                Max = max(Max,dp[i][j])
        return Max**2

还可以再优化，DP每个点的位置只与三个点有关。

    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix or not matrix[0]:
            return 0
        row = len(matrix)
        column = len(matrix[0])
        dp = [0]*(column + 1)
        maxlen = prev = 0
        for i in range(1, row+1):
            for j in range(1, column+1):
                temp = dp[j]
                if matrix[i-1][j-1] == '1':
                    dp[j] = min(dp[j-1], dp[j], prev) + 1
                else:
                    dp[j] = 0
                maxlen = max(maxlen,dp[j])
                prev = temp
        return maxlen**2