✔️ [Python3] MONOTONIC STACK t(-_-t), Explained
UPVOTE if you like (\uD83C\uDF38\u25E0\u203F\u25E0), If you have any question, feel free to ask.\n\nThe idea is to use a monotonic stack. We iterate over bars a
**UPVOTE if you like (\uD83C\uDF38\u25E0\u203F\u25E0), If you have any question, feel free to ask.**\n\nThe idea is to use a monotonic stack. We iterate over bars and add them to the stack as long as the last element in the stack is less than the current bar. When the condition doesn\'t hold, we start to calculate areas by popping out bars from the stack until the last element of the stack is greater than the current. The area is calculated as the number of pops multiplied by the height of the popped bar. On every pop, the height of the bar will be less or equal to the previous (since elements in the stack are always monotonically increasing).\n\nNow let\'s consider this example `[2,1,2]`. For this case the formula for the area (number of pops * current height) won\'t work because when we reach `1` we will pop out `2` from the stack and will not consider it later which is wrong since the largest area here is equal to `3 * 1`, i.e we somehow need to remember the previously discarded bars that still can form areas. We solve this problem by storing in the stack the width of the bar as well. So for our example, after discarding `2`, we push to the stack the `1` with the width equal to `2`.\n\nTime: **O(n)** - In the worst case we have 2 scans: one for the bars and one for the stack\nSpace: **O(n)** - in the wors case we push to the stack the whjole input array\n\nRuntime: 932 ms, faster than **51.27%** of Python3 online submissions for Largest Rectangle in Histogram.\nMemory Usage: 28.4 MB, less than **30.61%** of Python3 online submissions for Largest Rectangle in Histogram.\n\n```\ndef largestRectangleArea(self, bars: List[int]) -> int:\n\tst, res = [], 0\n\tfor bar in bars + [-1]: # add -1 to have an additional iteration\n\t\tstep = 0\n\t\twhile st and st[-1][1] >= bar:\n\t\t\tw, h = st.pop()\n\t\t\tstep += w\n\t\t\tres = max(res, step * h)\n\n\t\tst.append((step + 1, bar))\n\n\treturn res\n```\n\n**UPVOTE if you like (\uD83C\uDF38\u25E0\u203F\u25E0), If you have any question, feel free to ask.**
['Monotonic Stack', 'Python3']