Python by monotone stack [w/ Comment]
Python by monotone stack \n\n---\n\nImplementation:\n\n\nclass Solution:\n    def largestRectangleArea(self, heights: List[int]) -> int:\n        \n        # st
Python by monotone stack \n\n---\n\n**Implementation**:\n\n```\nclass Solution:\n    def largestRectangleArea(self, heights: List[int]) -> int:\n        \n        # store x coordination, init as -1\n        stack = [ -1 ]\n        \n        # add zero as dummy tail \n        heights.append( 0 )\n        \n        # top index for stack\n        top = -1\n        \n        # area of rectangle\n        rectangle = 0\n        \n        # scan each x coordination and y coordination\n        for x_coord, y_coord in enumerate(heights):\n            \n            while heights[ stack[top] ] > y_coord:\n            # current height is lower than previous\n            # update rectangle area from previous heights\n                \n                # get height\n                h = heights[ stack.pop() ]\n                \n                # compute width\n                w = x_coord - stack[top] -1 \n                \n                # update maximal area\n                rectangle = max(rectangle, h * w)\n                \n            # push current x coordination into stack\n            stack.append( x_coord )\n            \n        \n        return rectangle\n```
['Math', 'Monotonic Stack', 'Python', 'Python3']