[Python] increasing stack, explained
Key insight: for given bar i with value h, how to find the biggest rectangle, which is ending with this bar?  We need to find the previous smallest place, where
**Key insight**: for given bar `i` with value `h`, how to find the biggest rectangle, which is ending with this bar?  We need to find the previous smallest place, where value is less or equal than `h`: that is smallest `j`, such that `j < i` and `heights[j] >= heights[i]`. Ideal data structure for these type of problems is monostack: stack which has the following invariant: elements inside will be always in increasing order. To be more clear let us consired the following histogram `[1,4,2,5,6,3,2,6,6,5,2,1,3]`. Let us go element by element and understand what is going on.\n\n1. Stack is empty, so just put first bar of our histogram into stack: so we have `stack = [1]`. (actually what we put inside are indexes of bars, not values, but here we look at values for simplicity).\n2. Next we put bar `4`, and we have `[1, 4]` now. \n3. Next, we have bar `2`, which is less than `4`. So, first we evaluate When we evaluate `H` and `W`: width and height rectangle we can construct, using last element of stack as height: they equal to `4` and `1`. Next, we extract `4` and add `2` to stack, so we have `[1, 2]` bars in stack now.\n4. Next bar is bigger than `2`, so just add it and we have `[1, 2, 5]`\n5. Next bar is bigger than `5`, so just add it and we have `[1, 2, 5, 6]`\n6. Next bar is `3`, so we need to extract some stuff from our stack, until it becomes increasing one. We extract `6`, evaluate `(H, W) = (6, 1)` and extract `5` and evaluate `(H, W) = (5, 2)`. Now we have `[1, 2, 3]` in our stack.\n7. Next bar is `2`, it is smaller than `stack[-1]`, so we again need to extract some stuff: we extract `3` and have  `(H, W) = (3, 3)` and also we extract `2` and have  `(H, W) = (2, 5)`. Note here, why exactly we have `W = 5`: because we keep in stack indexes of our bars, and we can evaluate width as `i - stack[-1] - 1`. Now, we have `stack = [1, 2]`\n8. Next bar is `6`, so just put it to stack and we have `stack = [1, 2, 6]`.\n9. Next bar is `6` also, and we need to extract one last element from stack and put this new `6` to stack. `(H, W) = (6, 1)`. Note, that we have in stack `[1, 2, 6]` again, but it is values, for indexes last index was increased by one.\n10. Next bar is `5`, we extract last element from stack, have `(H, W) = (6, 2)` and put it to stack, so we have `[1, 2, 5]` now.\n11. Next bar is `2`, so we again start to pop elements to keep increasing order: `(H, W) = (5, 3)` for fisrt step and `(H, W) = (2, 9)` for second step, now `stack = [1, 2]`.\n12. Next bar is `1`, so we have `(H, W) = (2, 10)` and then `(H, W) = (1, 11)` and `stack = [1]`.\n13. Next bar is `3`, so we just put it to stack and have `[1, 3]` in stack.\n14. Next bar is `0` (we added it to process border cases), so we have `(H, W) = (3, 1)` and `(H, W) = (1, 13)` and finally stack is empty.\n\n**Complexity** is `O(n)`, where `n` is number of bars, space complexity is `O(n)` as well.\n\n```\nclass Solution:\n    def largestRectangleArea(self, 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\nSee also similar problems with monostack idea:\n\n**239.** Sliding Window Maximum https://leetcode.com/problems/sliding-window-maximum/discuss/951683/Python-Decreasing-deque-short-explained\n**496.** Next Greater Element I\n**739.** Daily Temperatures\n**862.** Shortest Subarray with Sum at Least K\n**901.** Online Stock Span\n**907.** Sum of Subarray Minimums\n**1687.** Delivering Boxes from Storage to Ports\n\n**Please let me know if you know more problems with this idea**\n\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Monotonic Stack']