2021-11-8-最大矩形

def f(mat):
    if len(mat) == 0:
        return 0

    m,n = len(mat), len(mat[0])
	# 用来算这个点开始1的最长
    left = [[0]*n for _ in range(m)]

    for i in range(m):
        left[i][0] = 1 if mat[i][0] == "1" else 0

    for i in range(m):
        for j in range(1,n):
            if mat[i][j] == '0':
                left[i][j] = 0
            else:
                left[i][j] = left[i][j-1] + 1

    ans = 0
    for i in range(m):
        for j in range(n):
            w = left[i][j]
            k = i
            area = w
			# 计算从这个端点的面积
            while k > 0:
                k -= 1
                if left[k][j] == 0:
                    break
                w = min(w, left[k][j])
                area = max(area, w*(i-k+1))
            ans = max(ans, area)
    return ans