class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        W = len(matrix)
        if W == 0:
            return 0
        H = len(matrix[0])


        heights = [0] * W
        ans = 0

        def get_extensions(r: Iterator[int]):
            nonlocal heights
            exts = []
            monostack = []
            for i in r:
                cur = heights[i]
                count = 1
                while monostack and monostack[-1][0] >= cur:
                    _, mcount = monostack.pop()
                    count += mcount
                monostack.append([cur, count])
                exts.append(monostack[-1][1])
            return exts

        for y in range(H):
            for x in range(W):
                heights[x] = 0 if matrix[x][y] == "0" else heights[x] + 1

            left = get_extensions(range(W))
            right = get_extensions(range(W - 1, -1, -1))
            ans = max(
                ans,
                max((left[i] + right[W - 1 - i] - 1) * heights[i] for i in range(W)),
            )

        return ans