Python Easy Solution (beats 96%)
\n\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nUse ascending monotonic stack to solve this.\n\n# Approach\n Describe your appr
![image.png](https://assets.leetcode.com/users/images/2c3ae17b-199f-4484-8ea6-1d9f9f4417f8_1686677923.8759806.png)\n\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse ascending monotonic stack to solve this.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- store a tuple: (index, val) in monotonic stack. This will make our idea clear and benefit our explanation\n- use ascending stack instead of descending stack\n- remember to record minStartIdx while poping stack. Otherwise, the solution can\'t tackle with inputs like: [2,1,2]. I saw many solutions are lack of this step, technically they are wrong. But it\'s weird that they can pass the submission. \n- when encounter the equal problem (current Height == height of stack top), we don\'t need to push it into the stack, since the area calculation will be coverd by the current stack top element.\n- appending a small number (0 or -1) at the end of the input array can efficiently solve non-empty stack problems. We can avoid writing extra code after the for/while loop to empty the stack.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n# Code\n```\nclass Solution:\n    def largestRectangleArea(self, heights: List[int]) -> int:\n        maxArea = 0\n        stack = [] # startIdx, height\n        heights.append(0) # allows us to clear out stack without extra logic\n        for curI, curH in enumerate(heights):\n            # don\'t need to append if we already have the value with a lower startIdx\n            if stack and curH == stack[-1][1]:\n                continue\n            minStartIdx = curI\n            while stack and curH < stack[-1][1]:\n                startIdx, lastHeight = stack.pop()\n                minStartIdx = startIdx\n                maxArea = max(maxArea, lastHeight * (curI - startIdx))\n            stack.append((minStartIdx, curH))\n        return maxArea\n```
['Monotonic Stack', 'Python3']