class Solution(object):
    def maximalRectangle(self, matrix):
        if not matrix or len(matrix) == 0: return 0
        res, rows, columns = 0, len(matrix), len(matrix[0])
        for r in xrange(rows):
            for c in xrange(columns):
                if r == 0: matrix[r][c] = int(matrix[r][c])
                else:
                    if matrix[r][c] == '1': matrix[r][c] = 1 + matrix[r - 1][c]
                    else: matrix[r][c] = 0
            res = max(res, self.largestRectangleArea(matrix[r]))
        return res

    def largestRectangleArea(self, heights):
        stack, res, i, n = [], 0, 0, len(heights)
        while i <= n:
            if i == n: h = 0
            else: h = heights[i]

            if len(stack) == 0 or h >= heights[stack[-1]]:
                stack.append(i)
                i += 1
            else:
                curr = heights[stack.pop()]
                if len(stack) == 0: res = max(res, curr * i)
                else: res = max(res, curr * (i - 1 - stack[-1]))
        return res