[LeetCode] Largest Rectangle in Histogram

leetcode

This problem is similar to Trapped Water.
Initial thought will be for each bar, try to find the bounds of right and left
However this takes O(n^2) way too long
Instead of trying to find each time, we can use a stack to memorize the history height and position

We only calculate the size when we see a bar the lower than previous ones
Because we know that it’s impossible for the previous height to sustain
However there’s one thing to remember:
When we pop the previous elements, keep the position in stack
Because although the height cannot be sustained, the future rectangle can still count it. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        loc = []
        stack = []
        ans = 0
        for i, e in enumerate(heights):
            if i == 0 or e >= stack[-1]:
                loc.append(i)
                stack.append(e)
            else:
                # pop and calculate
                while len(stack) > 0 and e < stack[-1]:
                    h = stack.pop()
                    start = loc.pop()
                    size = h * (i - start)

                    if size > ans: ans = size
                loc.append(start)
                stack.append(e)

        while len(stack) > 0:
            h = stack.pop()
            start = loc.pop()
            size = h * (len(heights) - start)
            if size > ans: ans = size
        return ans