Python solution with detailed explanation
Solution with discussion https://discuss.leetcode.com/topic/77574/python-solution-with-detailed-explanation\n\nLargest Rectangle in Histogram https://leetcode.c
**Solution with discussion** https://discuss.leetcode.com/topic/77574/python-solution-with-detailed-explanation\n\n**Largest Rectangle in Histogram** https://leetcode.com/problems/largest-rectangle-in-histogram/\n\nhttp://www.geeksforgeeks.org/largest-rectangle-under-histogram/\nhttp://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/\n\n1. For every bar \u2018x\u2019, we calculate the area with \u2018x\u2019 as the smallest bar in the rectangle. \n2. If we calculate such area for every bar \u2018x\u2019 and find the maximum of all areas, our task is done. \n3. How to calculate area with \u2018x\u2019 as smallest bar? We need to know index of the first smaller (smaller than \u2018x\u2019) bar on left of \u2018x\u2019 and index of first smaller bar on right of \u2018x\u2019. Let us call these indexes as \u2018left index\u2019 and \u2018right index\u2019 respectively.\n4. We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. \n5. A bar is popped from stack when a bar of smaller height is seen. \n6. When a bar is popped, we calculate the area with the popped bar as smallest bar. \n7. **How do we get left and right indexes of the popped bar \u2013 the current index tells us the \u2018right index\u2019 and index of previous item in stack is the \u2018left index\u2019. Note index of previous item is important here.** \n8. Now using the above idea, we can make both an N^2 and NlgN algorithm.\n9. For N^2 algorithm, no stack is requried. We scan at each step in left and right direction.\n10. For NlgN algorithm, we find the minimum height m1. We then split at the minimum height.\n\n```\nclass Solution(object):\n    def largestRectangleArea(self, heights):\n        """\n        :type heights: List[int]\n        :rtype: int\n        """\n        max_area, st = 0, []\n        for idx,x in enumerate(heights):\n            if len(st) == 0:\n                st.append(idx)\n            elif x >= heights[st[-1]]:\n                st.append(idx)\n            else:\n                while st and heights[st[-1]] > x:\n                    # For min_height, the right index is idx and the left index is st[-1].\n                    # Distance between them will be (right_index - left_index - 1). right & left index are not included in result.\n                    # If the stack is empty, then no bar on left is smaller. So width of base is idx.\n                    min_height = heights[st.pop()] \n                    max_area = max(max_area, min_height*(idx-1-st[-1])) if st else max(max_area, min_height*idx)\n                st.append(idx)\n        while st:\n            min_height = heights[st.pop()] \n            max_area = max(max_area, min_height*(len(heights)-1-st[-1])) if st else max(max_area, min_height*len(heights))\n        return max_area\n```
[]