https://leetcode.com/problems/largest-rectangle-in-histogram

Key insight: for given bar i with value h, how to find the biggest rectangle, which is ending with this bar? We need to find the previous smallest place, where value is less or equal than h: that is smallest j, such that j < i and heights[j] >= heights[i]. Ideal data structure for these type of problems is monostack: stack which has the following invariant: elements inside will be always in increasing order. To be more clear let us consired the following histogram [1,4,2,5,6,3,2,6,6,5,2,1,3]. Let us go element by element and understand what is going on.

  1. Stack is empty, so just put first bar of our histogram into stack: so we have stack = [1]. (actually what we put inside are indexes of bars, not values, but here we look at values for simplicity).
  2. Next we put bar 4, and we have [1, 4] now.
  3. Next, we have bar 2, which is less than 4. So, first we evaluate When we evaluate H and W: width and height rectangle we can construct, using last element of stack as height: they equal to 4 and 1. Next, we extract 4 and add 2 to stack, so we have [1, 2] bars in stack now.
  4. Next bar is bigger than 2, so just add it and we have [1, 2, 5]
  5. Next bar is bigger than 5, so just add it and we have [1, 2, 5, 6]
  6. Next bar is 3, so we need to extract some stuff from our stack, until it becomes increasing one. We extract 6, evaluate (H, W) = (6, 1) and extract 5 and evaluate (H, W) = (5, 2). Now we have [1, 2, 3] in our stack.
  7. Next bar is 2, it is smaller than stack[-1], so we again need to extract some stuff: we extract 3 and have (H, W) = (3, 3) and also we extract 2 and have (H, W) = (2, 5). Note here, why exactly we have W = 5: because we keep in stack indexes of our bars, and we can evaluate width as i - stack[-1] - 1. Now, we have stack = [1, 2]
  8. Next bar is 6, so just put it to stack and we have stack = [1, 2, 6].
  9. Next bar is 6 also, and we need to extract one last element from stack and put this new 6 to stack. (H, W) = (6, 1). Note, that we have in stack [1, 2, 6] again, but it is values, for indexes last index was increased by one.
  10. Next bar is 5, we extract last element from stack, have (H, W) = (6, 2) and put it to stack, so we have [1, 2, 5] now.
  11. Next bar is 2, so we again start to pop elements to keep increasing order: (H, W) = (5, 3) for fisrt step and (H, W) = (2, 9) for second step, now stack = [1, 2].
  12. Next bar is 1, so we have (H, W) = (2, 10) and then (H, W) = (1, 11) and stack = [1].
  13. Next bar is 3, so we just put it to stack and have [1, 3] in stack.
  14. Next bar is 0 (we added it to process border cases), so we have (H, W) = (3, 1) and (H, W) = (1, 13) and finally stack is empty.

Complexity is O(n), where n is number of bars, space complexity is O(n) as well.

class Solution:
    def largestRectangleArea(self, heights):
        stack, ans = [], 0
        for i, h in enumerate(heights + [0]):
            while stack and heights[stack[-1]] >= h:
                H = heights[stack.pop()]
                W = i if not stack else i-stack[-1]-1
                ans = max(ans, H*W)
            stack.append(i)
        return ans

See also similar problems with monotonic deque idea:

239. Sliding Window Maximum 496. Next Greater Element I 739. Daily Temperatures 862. Shortest Subarray with Sum at Least K 901. Online Stock Span 907. Sum of Subarray Minimums 1687. Delivering Boxes from Storage to Ports

Please let me know if you know more problems with this idea

If you like the solution, you can upvote it on leetcode discussion section: Problem 0084