最大正方形

题目要求

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

输入: 

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

输出: 4

思路分析

只包含1的正方形可以出现在矩阵的任意位置，所以，不要妄想通过什么巧妙的办法快速的找到这个正方形的位置，正确的做法是遍历整个矩阵，尝试去找正方形，可能会找到多个，因此还要保留记录那个最大的正方形。

既然是遍历，那么就得从头到尾的进行遍历，假设矩阵matrix大小是M*N，那么就从matrix[0][0]开始进行遍历，一直遍历到matrix[M-1][N-1]。

当遍历到matrix[x][y]时，可以将这个点视为正方形的左上角，以此为基础，去判断matrix[x+1][y]， matrix[x][y+1]， matrix[x+1][y+1]这3个点是否也是1，如果成立，就找到了一个正方形，在此基础上，再向右下方扩展一层，判断能否以matrix[x][y]做正方形的左上角，以matrix[x+2][y+2]做正方形的右下角。

由于总是以某个点做正方形的左上角，因此，最后一行和最后一列是不需要遍历的，因为这些点无法构成正方形的左上角。

示例代码

matrix = [
    [1, 0, 1, 0, 0],
    [1, 0, 1, 1, 1],
    [1, 1, 1, 1, 1],
    [1, 0, 1, 1, 1],
    [1, 0, 1, 1, 1],
]

matrix = [['1']]

def max_square(matrix):
    y = len(matrix)
    if y == 0:
        return 0

    x = len(matrix[0])
    if x == 0:
        return 0

    max_area = 0
    for i in range(0, y):
        for j in range(0, x):
            cell = matrix[i][j]
            if cell == '0':
                continue

            area = get_area(matrix, i, j)
            if area > max_area:
                max_area = area

    return max_area


def get_area(matrix, left_up_x, left_up_y):
    step = 1
    right_down_x = left_up_x + step
    right_down_y = left_up_y + step

    while right_down_x < len(matrix) and right_down_y < len(matrix[0]):
        b_square = True
        if matrix[right_down_x][right_down_y] == '0':
            break

        for i in range(left_up_x, right_down_x):
            if matrix[i][right_down_y] == '0':
                b_square = False
                break

        if not b_square:
            break

        for j in range(left_up_y, right_down_y):
            if matrix[right_down_x][j] == '0':
                b_square = False
                break

        if not b_square:
            break

        step += 1
        right_down_x = left_up_x + step
        right_down_y = left_up_y + step


    return step**2


if __name__ == '__main__':
    print(max_square(matrix))