[Python] A brief summary for Monotonous Stacks applications
For this problem, an monotonously increasing stack is used to store the previous indices. Once current height < stack[-1]\'s height, a cadidate rectangler area 
For this problem, an monotonously increasing stack is used to store the previous indices. Once `current height` < `stack[-1]\'s height`, a cadidate rectangler area can be calculated with `width: length between stack[-2] + 1 ~ current index - 1`, `height: stack[-1]\'s height`. Compare all candidates to get the final results. \n```\nclass Solution(object):\n    def largestRectangleArea(self, heights):\n        """\n        :type heights: List[int]\n        :rtype: int\n        """\n        heights.append(0)\n        inStack, rst = [], 0\n        for i in range(len(heights)):\n            while inStack and heights[i] < heights[inStack[-1]]:\n\t\t\t    # local regionMin\'s idx, where the `local region` is [last.last.idx + 1, cur.idx - 1]\n                regionMinIdx = inStack.pop()\n                h = heights[regionMinIdx]\n\t\t\t\t# width = endIdx - startIdx + 1 if there is a start, else endIdx - 0 + 1\n                w = i - 1 - (inStack[-1] + 1) + 1 if inStack else i - 1 - 0 + 1\n                rst = max(rst, h * w)\n            inStack.append(i)\n        return rst\n```\n\nBesides this one, monotonous stack can solve other problems with **a similiar template**. \n1.  [Locate days between today and next warmer day](https://leetcode.com/problems/daily-temperatures/discuss/109832/Java-Easy-AC-Solution-with-Stack): it can be used when finding first largest element. \n```py\nclass Solution(object):\n    def dailyTemperatures(self, T):\n        """\n        :type T: List[int]\n        :rtype: List[int]\n        """\n        deStack = []\n        rst = [0] * len(T)\n        for i in range(len(T) - 1, -1, -1):\n            while deStack and T[i] >= T[deStack[-1]]:\n                deStack.pop()\n            rst[i] = deStack[-1] - i if deStack else 0\n            deStack.append(i)\n        return rst\n```\n2.  [Trapping rain water stack solution](https://leetcode.com/problems/trapping-rain-water/solution/): it can be used when finding `leftmost first larger element` **AND** the `rightmost first larger element` in one pass. \n```py\nclass Solution(object):\n    def trap(self, height):\n        """\n        :type height: List[int]\n        :rtype: int\n        """\n        # stack recording decreasing height\'s indices\n        # each time cur height > last height, update the rectangular region last.last.Idx -> curIdx, last.Height -> min(last.last.Height, cur.Height)\n        deStack = []\n        rst = 0\n        for curIdx, curHeight in enumerate(height):\n            while deStack and curHeight > height[deStack[-1]]:\n                lastIdx = deStack.pop()\n                if deStack:\n                    rst += (curIdx - deStack[-1] - 1) * (min(curHeight, height[deStack[-1]]) - height[lastIdx])\n            # Only processed prev rectangular blocks with left bar < curHeight, cur position might still able to keep \n            # rain water so curIdx still need to be pushed in stack\n            deStack.append(curIdx)\n        return rst\n```\n3.  [Minimum cost construct Tree from Leaf values](https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/discuss/339959/One-Pass-O(N)-Time-and-Space): still, use it to find left and right first larger element. Also a, **wrong-result**, increasing instead of decreasing stack solution can be found [here](https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/discuss/574870/Python-Two-Monotonous-Stack-solutions%3A-decreasing-and-increasing-stacks) for practice.\n```py\nclass Solution(object):\n    def mctFromLeafValues(self, arr):\n        """\n        :type arr: List[int]\n        :rtype: int\n        """\n        # Each number A can be removed by its left/right largest(or smallest depending on removing from small -> large or large -> small) adjacent number with cost A * left/right, \n        # smallest cost to remove A would be A * min(left, right)\n        # remove num with its min(left/right FIRST larger number)\n        cost, n = 0, len(arr)\n        arr.append(sys.maxsize)  # add a large number at the end to pop out all final decreasing nums\n        deStack = []  # decreasing stack\n        for i, num in enumerate(arr):\n            while deStack and num >= deStack[-1]:\n                val = deStack.pop()\n                if deStack or i != n:\n                    cost += val * min(num, deStack[-1]) if deStack else val * num\n            deStack.append(num)\n        return cost\n```\n4. [Asteroid merging](https://leetcode.com/problems/asteroid-collision/discuss/580582/Python-Stack-solution-WITHOUT-uninterpretable-nested-loops): monotonous stack is not limited to be used on finding first larger/smaller item. It can be extended on other tasks when only single direction expantion/updating is allowed and the `monotonous` feature can also mean for the increasing absolute value or other more abstract self-defined concepts.\n```py\nclass Solution(object):\n    def asteroidCollision(self, asteroids):\n        """\n        :type asteroids: List[int]\n        :rtype: List[int]\n        Note: -5, 5, -3, 5 -> -5 5 5, the head wont merge with the tail\n        """\n        s = []\n        def inner(cur):\n            append_cur = True\n            # inner loop is to backwardly delete s, cur is not moving at inner loop.\n            while s and cur < 0 and s[-1] > 0:\n                if abs(cur) > s[-1]:\n                    s.pop()\n                    continue  # to delete more s\'s ending positive numbers\n                elif abs(cur) == s[-1]:\n                    s.pop()\n                    append_cur = False  # equal, cur is disposed\n                    break\n                else:\n                    append_cur = False  # |cur| < s[-1], cur is disposed\n                    break\n            return append_cur\n                    \n        \n        for cur in asteroids:\n            append_cur = inner(cur)\n            if append_cur:\n                s.append(cur)\n        return s\n```
[]