讨论/《算法与面试技巧精讲》 - 最大矩形/
《算法与面试技巧精讲》 - 最大矩形
class Solution:
    '''
    方法:使用柱状图的优化暴力方法
    我们首先计算出矩阵的每个元素的左边连续 1 的数量, 使用二维数组 left[m][n] 记录, 其中 m, n 就是原来矩阵的行数和列数, left[i][j] 就是矩阵第 i 行第 j 列元素左边连续 1 的数量(含自己)。
    对left矩阵, 如果按列遍历, 这实际上就是题目 84 中的柱状图,不过这个柱状图里面的每个柱子高度都是指原来矩阵 i, j 元素左边连续 1 的数量(含自己)
    至此, 我们可以对left矩阵按列遍历, 对每列left矩阵形成的柱状图使用 84 题中的单调栈的方法求该柱状图可以形成的矩形的最大面积,
    然后求出不同柱状图返回的矩形最大面积的全局最大值。

    我们还可以对生成的柱状图采用暴力解法, 总之85题的重点就是先求出left矩阵。

    类似的, 我们还可以定义一个 above 矩阵, 这个矩阵跟 left 矩阵类似,above[i][j] 就是矩阵第 i 行第 j 列元素正上方连续 1 的数量(含自己)。
    然后再对 above 矩阵按行扫描,每一行就是一个柱状图,然后再对每个柱状图求该柱状图的最大面积,然后再求出所有柱状图之间的全局最大值
    '''
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if matrix == []:
            return 0
        left = [[0 for i in range(len(matrix[0]))] for i in range(len(matrix))]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == '0':
                    left[i][j] = 0
                else:
                    if j > 0:
                        left[i][j] = left[i][j - 1] + 1
                    else:
                        left[i][j] = 1

        # 至此 left 矩阵就已经生成完成了
        
        global_max_area = 0
        for j in range(len(left[0])):
            heights = [i[j] for i in left].copy()
            tmp_max_area = self.largestRectangleArea(heights)
            global_max_area = max(global_max_area, tmp_max_area)
        return global_max_area
    
    def largestRectangleArea(self, heights):
        stack = []
        new_heights = [0] + heights + [0]
        index = 0
        max_area = 0
        while index < len(new_heights):
            while stack != [] and new_heights[index] < new_heights[stack[-1]]:
                peek_height = new_heights[stack.pop(-1)]
                width = index - stack[-1] - 1
                tmp_area = peek_height * width
                max_area = max(max_area, tmp_area)
            stack.append(index)
            index += 1
        return max_area