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