Stack based O(N) with detailed explanation
Solution intuition\n\nThe idea to efficiently solve this problem is very simple. Let\'s say we have heights as follows:\n\n\n\nFor any particular height which w
## Solution intuition\n\nThe idea to efficiently solve this problem is very simple. Let\'s say we have heights as follows:\n\n![image](https://assets.leetcode.com/users/images/07c7cd76-4a44-4ff9-bfa3-fdc1f07c1c0e_1642218096.3927934.png)\n\nFor any particular height which we choose,\n\n![image](https://assets.leetcode.com/users/images/cdfcef1b-e144-49c2-87a5-df3714528d5a_1642218132.8541813.png)\n\nThe maximum area rectangle which includes this height is going to contain all heights to the left which are greater than or equal to the selected height and likewise for heights on the right. In this example, it would be:\n\n![image](https://assets.leetcode.com/users/images/b2a90570-4893-4cc6-80e0-b4dda58b75db_1642218211.9088748.png)\n\nSo, if we can efficiently precompute, for each index `i`, the number of heights to the left which are greater than or equal to `heights[i]` and the number of heights to the right which are greater or equal to `heights[i]`:\n\n![image](https://assets.leetcode.com/users/images/754bd699-a086-4c22-a47f-f14451a45027_1642218271.5627522.png)\n\nthen computing the area of the rectangle for each index `i` simply becomes:\n\n```\narea of rectangle of height heights[i] = heights[i] * (left[i] + right[i] + 1)\n```\nThe plus one is to include the bar for the selected height itself. If we have `left` and `right` precomputed then the max area can be computed in a single pass over `heights`.\n\n---\n\n## Computing left and right\n\nTo compute `left`, we can use a stack. The code is as follows:\n\n```py\nleft, stack = [0] * n, []\nfor i in range(n):\n    h, start = heights[i], i\n    while stack and h <= heights[stack[-1]]:\n        start = stack.pop()\n\n    left[i] = (i - start) + left[start]\n    stack.append(i)\n```\nWe push each index onto a stack as we go over them. For each index we also want to compute the number of consecutive heights to the left of the index which are all greater or equal to the height at the index.\n\nTo do so we keep popping indices off the stack until their heights at greater or equal to `heights[i]`. We add the difference between the current index `i` and the last popped index `start` to `left[i]`.\n\nBut when we processed the index at `start`, we may have popped off further values from the stack so we also need to account for that by adding `left[start]`.\n\nIf we don\'t pop anything off the stack then `start = i` so we simply get `left[i] = (i - i) + left[i]` which is zero as one would expect.\n\nThe final code, including `right` is:\n\n```py\nclass Solution:\n    def largestRectangleArea(self, heights: List[int]) -> int:\n        n = len(heights)\n\n        left, stack = [0] * n, []\n        for i in range(n):\n            h, start = heights[i], i\n            while stack and h <= heights[stack[-1]]:\n                start = stack.pop()\n\n            left[i] = (i - start) + left[start]\n            stack.append(i)\n\n        right, stack = [0] * n, []\n        for i in reversed(range(n)):\n            h, end = heights[i], i\n            while stack and h <= heights[stack[-1]]:\n                end = stack.pop()\n            \n            right[i] = (end - i) + right[end]\n            stack.append(i)\n\n        area = 0\n        for i, height in enumerate(heights):\n            width = right[i] + left[i] + 1\n            area = max(area, width * height)\n        return area\n```\n\n**Time complexity:** O(N)\n**Space complexity:** O(N)\n
['Stack', 'Python']