Python solution
Initialize an empty stack and iterate over the elements in heights. Suppose we are at index i, we can construct stack in such a way that it contains all the rec
Initialize an empty `stack` and iterate over the elements in `heights`. Suppose we are at index `i`, we can construct `stack` in such a way that it contains all the rectangles that started at an index `j <= i`, and can survive `i` (i.e., `height[j] <= height[i]`). By construction, the rectangles in `stack` will have a monotonic non-decreasing height. More specifically, at index `i`, we have the following possibilities:\n1. The `stack` is empty, in which case, we add `(i, heights[i])` into `stack`, i.e., a rectangle starting at `i` of height `heights[i]`.\n2. The `stack` is non-empty, and `stack[-1][1] <= heights[i]`, in which case all rectangles in the `stack` will be able to survive `i`, and we don\'t need to do anything about existing elements in `stack`. We just need to append `(i, heights[i])` to the `stack`.\n3. The `stack` is non-empty, and  `stack[-1][1] > heights[i]`, in which case rectangles in `stack` with height larger than `heights[i]` will not be able to survive `i`. So we keep popping the `stack` until it\'s empty or the last element of the stack has height no larger than `heights[i]`. Each time we pop `stack`, and get an element `(j, m)`, we need to update the `max_area`, because there is a rectangle of height `m` that started at `j` and end at `i - 1`, with area `(i - j) * m`, and it may well be the rectangle with the largest area. Finally, we need to append a rectangle `stack` of height `heights[i]`. To maximize its area, we want to make its starting point as small as possible. The smallest it can be is the starting point of the shortest rectangle that fails to survive `i`, which is the index of the last rectangle we popped from `stack`. So when finish `stack`, we just need to append `(j, heights[i])` to it.\n\nFinally, after iterating over `heights`, whatever that\'s left in `stack` are all the rectangles that managed to survive the last index of `heights`. So we just need to pop out each element `(j, m)` in `stack`, and check its area `(len(heights) - j) * m` is larger than `max_area`, and update `max_area` accordingly. After this, `max_area` is the desired solution to the problem.\n\nTime complexity: O(n), space complexity: O(n).\n\n```\nclass Solution:\n    def largestRectangleArea(self, heights: List[int]) -> int:\n        stack = []\n        max_area = 0\n        l = len(heights)\n        for i, n in enumerate(heights):\n            if not stack or stack[-1][1] <= n:\n                stack.append((i, n))\n            else:\n                while stack and stack[-1][1] > n:\n                    j, m = stack.pop()\n                    max_area = max(max_area, (i - j) * m)\n                stack.append((j, n))\n        \n        while stack:\n            j, m = stack.pop()\n            max_area = max(max_area, (l - j) * m)\n        return max_area\n```
[]