main idea: 0. be aware of edge case r == 0, c == 0 1. for each row, caculate accumulative height, 2 . use algorithm from LC75(caculate histogram max area) to caculte max area

class Solution:
# time O(R*C) space O(C)
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        r = len(matrix)
        c = len(matrix[0])
        if c == 0:
            return 0
        maxArea = -1
        height = [0] * c 
        for i in range(r):
            for j in range(c):
                if matrix[i][j] == "1":
                    height[j] += 1
                else:
                    height[j] = 0
            area = self.largestRectangleArea(height)
            maxArea = max(area,maxArea)
        return maxArea
    def largestRectangleArea(self, H):
        st = [-1]
        res = 0
        H.append(0)
        n = len(H)
        for i in range(n):
            while H[i] < H[st[-1]]:
                #print(st)
                h = H[st.pop()]
                w = i -st[-1] - 1
                #print(h,w,st)
                res = max(h*w,res)
            st.append(i)
        H.pop()
        return res