[Python] O(mn) solution, explained
There is dp O(n^2m^2) solution. We can do better, with O(nm*min(m,n)) complexity, if we use dynamic programming and keep two tables: h[i][j] is the largest L, s
There is dp `O(n^2m^2)` solution. We can do better, with `O(nm*min(m,n))` complexity, if we use dynamic programming and keep two tables: `h[i][j]` is the largest `L`, such that all elements in `A[i:i+L-1][j] = 1`, and similar `w[i][j]`. Then we go through our original table `A` and we can calculate for `A[i][j]` the largest subarray that has `A[i][j]` as its bottom-left corner, it can be done with `O(n)` iterations.\n\nFinally, there is very smart way with complexity `O(nm)`, using problem **0084**. Indeed, for each row we can evaluate our skyline heights, given previous row in `O(m)` and do it `n` times. Additional complexity is `O(m)`, because actually we need to keep only one row at at time.\n\n#### Complexity\nIt is `O(nm)` for time and `O(m)` for space.\n\n#### Code\n```python\nclass Solution:\n    def maximalRectangle(self, matrix):\n        def hist(heights):\n            stack, ans = [], 0\n            for i, h in enumerate(heights + [0]):\n                while stack and heights[stack[-1]] >= h:\n                    H = heights[stack.pop()]\n                    W = i if not stack else i-stack[-1]-1\n                    ans = max(ans, H*W)\n                stack.append(i)\n            return ans\n        \n        if not matrix or not matrix[0]: return 0\n        m, n, ans = len(matrix[0]), len(matrix), 0\n        row = [0]*m\n        for i in range(n):\n            for j in range(m):\n                row[j] = 0 if matrix[i][j] == "0" else row[j] + 1\n            ans = max(ans, hist(row))\n            \n        return ans\n```\n\nIf you have any question, feel free to ask. If you like the explanations, please **Upvote!**\n
['Monotonic Stack']