[Python] Simple Stack Solution
Key Insights:\n\nFor each index, the largest rectangle of heights h[i] that passes\nthrough the index will have a left bound at the first height lower\nthan h[i
**Key Insights:**\n\nFor each index, the largest rectangle of heights h[i] that passes\nthrough the index will have a left bound at the first height lower\nthan h[i] to the left and a right bound at the first height lower than\nh[i] to the right.\n\n**Approach:**\n\nFor each index:\n1. Find the index of the first shorter building that is to the left\n2. Find the index of the first shorter building that is to the right\n3. The rectangle area is heights[i] * (right[i] - left[i] - 1)\n\n**Implementation:**\n\nUse a stack approach to find the index of the first building shorter\nthan heights[i] to the right of index i.\n\nThen reverse heights and repeat the process to find the first\nbuilding shorter than heights[i] to the left of i.\n\n<br>\n\n```python\ndef largestRectangleArea(self, heights: List[int]) -> int:\n\n\tif not heights: return 0\n\tn = len(heights)\n\t\n\t# 1. Index of the first building shorter than heights[i] to the right of i\n\tright = [n] * n\n\tstack = []\n\tfor i, h in enumerate(heights):\n\t\twhile stack and h < stack[-1][1]:\n\t\t\tright[stack.pop()[0]] = i\n\t\tstack.append((i, h))\n\n\t# 2. Index of the first building shorter than heights[i] to the left of i\n\tleft = [-1] * n\n\tstack = []\n\tfor i in range(n - 1, -1, -1):\n\t\th = heights[i]\n\t\twhile stack and h < stack[-1][1]:\n\t\t\tleft[stack.pop()[0]] = i\n\t\tstack.append((i, h))\n\n\tarea = [heights[i] * (right[i] - left[i] - 1) for i in range(n)]\n\treturn max(area)\n```
[]