85

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:

        def max_hist_area(col):
            n = len(matrix)
            prev_lt = [i for i in range(n)]
            st_prev = []
            next_lt = [n - i - 1 for i in range(n)]
            st_next = []

            for row in range(n):
                while st_prev and matrix[row][col] <= matrix[st_prev[-1]][col]:
                    st_prev.pop()
                if st_prev:
                    prev_lt[row] = row - st_prev[-1] - 1
                st_prev.append(row)

                while st_next and matrix[row][col] < matrix[st_next[-1]][col]:
                    x = st_next.pop()
                    next_lt[x] = row - x - 1
                st_next.append(row)

            res = 0

            for row in range(n):
                res = max(res, (1 + prev_lt[row] + next_lt[row]) * matrix[row][col])

            return res


        for i in range(len(matrix)):
            cur_max = 0
            for j in range(len(matrix[i])):
                if matrix[i][j] == '1':
                    matrix[i][j] = cur_max + 1
                    cur_max += 1
                else:
                    matrix[i][j] = 0
                    cur_max = 0

        res = 0
        if matrix:
            for col in range(len(matrix[0])):
                res = max(res, max_hist_area(col))

        return res