[Python] Stack Solution O(N) Time - using approach of Next Smaller to Left and Right
\nclass Solution:\n    def largestRectangleArea(self, heights: List[int]) -> int:\n        n = len(heights)\n        # left boundary => next smaller element to 
```\nclass Solution:\n    def largestRectangleArea(self, heights: List[int]) -> int:\n        n = len(heights)\n        # left boundary => next smaller element to left\n        stack = []\n        nextSmallerLeft = [0]*n\n        for i in range(n):\n            while stack and heights[stack[-1]] >= heights[i]:\n                stack.pop()\n            if stack:\n                nextSmallerLeft[i] = stack[-1] + 1\n            stack.append(i)\n        \n        # right boundary => next smaller element to right\n        stack = []\n        nextSmallerRight = [n-1]*n\n        for i in range(n-1, -1, -1):\n            while stack and heights[stack[-1]] >= heights[i]:\n                stack.pop()\n            if stack:\n                nextSmallerRight[i] = stack[-1] - 1\n            stack.append(i)\n        \n        res = heights[0]\n        for i in range(n):\n            height = heights[i]\n            weidth = nextSmallerRight[i] - nextSmallerLeft[i] + 1\n            area = height * weidth\n            res = max(res, area)\n            \n        return res\n\t\t\n\t\t\n# Time: O(N)\n# Space: O(N)\n```\n
['Stack', 'Monotonic Stack', 'Python', 'Python3']