[Python] Based on Maximum Rectangle in Histogram - Clean & Concise
Idea\n- Sub problem of this problem is: 84. Largest Rectangle in Histogram\n- So, instead of solving sub-matrix problems, we can change to solve by sub-array pr
**Idea**\n- Sub problem of this problem is: [84. Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)\n- So, instead of solving sub-matrix problems, we can change to solve by sub-array problems.\n\n```python\nclass Solution:\n    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n        if len(matrix) == 0: return 0\n        m, n = len(matrix), len(matrix[0])\n        dp = [0] * n\n        maxArea = 0\n        for r in range(m):\n            for c in range(n):\n                if matrix[r][c] == "1":\n                    dp[c] += 1\n                else:\n                    dp[c] = 0\n            maxArea = max(maxArea, self.maxRectangleInHistogram(dp))\n        return maxArea\n\n    def maxRectangleInHistogram(self, heights):  # O(N)\n        n = len(heights)\n        st = [-1]\n        maxArea = 0\n        for i in range(n):\n            while st[-1] != -1 and heights[st[-1]] >= heights[i]:\n                currentHeight = heights[st.pop()]\n                currentWidth = i - st[-1] - 1\n                maxArea = max(maxArea, currentWidth * currentHeight)\n            st.append(i)\n        while st[-1] != -1:\n            currentHeight = heights[st.pop()]\n            currentWidth = n - st[-1] - 1\n            maxArea = max(maxArea, currentWidth * currentHeight)\n        return maxArea\n```\n\nComplexity:\n- Time: `O(R * C)`\n- Space: `O(C)`
[]