python O(n) explained in detail
\nclass Solution(object):\n    def largestRectangleArea(self, heights):\n        """\n        :type heights: List[int]\n        :rtype: int\n        """\n      
```\nclass Solution(object):\n    def largestRectangleArea(self, heights):\n        """\n        :type heights: List[int]\n        :rtype: int\n        """\n        # for every bar, calc the area which uses this bar as the lowest bar\n        # therefore we need to find the first lower bar towards the left and the \n        # first lower bar towards the right\n        # hence, we need a stack to keep stacking the higher bars\n        # when a lower bar appears, thats the first lower bar towards the right\n        # and the first lower bar towards the left will be the next bar in the stack\n        stack = []\n        max_area = 0\n        for i in range(len(heights)):\n            if not stack:\n                stack.append(i)\n            else:\n                # if height not decreasing, just stack\n                if heights[i] >= heights[stack[-1]]:\n                    stack.append(i)\n                    continue\n                while stack and heights[i] < heights[stack[-1]]:\n                    # for the bar on top of the stack\n                    # we found the first lower bar towards the right\n                    this_bar = stack.pop()\n                    right_index = i\n                    left_index = stack[-1] if stack else -1 # no lower towards the left, so make it left of the leftmost, which makes it -1\n                    area = heights[this_bar] * (right_index - left_index -1)\n                    max_area = max(area, max_area)\n                stack.append(i)\n        while stack:\n            this_bar = stack.pop()\n            right_index = len(heights) # no lower towards the right, so make it right of the rightmost, which makes it len(heights)\n            left_index = stack[-1] if stack else -1\n            area = heights[this_bar] * (right_index - left_index -1)\n            max_area = max(area, max_area)\n        return max_area \n```
[]