Largest Rectangle In Histogram

[darwinrlo]

LeetCode

[darwinrlo]

Create a stack. Push -1 onto it. This -1 will never be popped. If we pop an element from the stack and only -1 is left on the stack, then the rectangle should extend as far left as it can. The width then is the distance from the end of -1 to the start of the current element (which could be the end of the array).

Iterate through the elements for the array. For each element:

• If the stack is empty or if the current element is >= the top stack element, then push the element to the stack.
• Otherwise, pop the stack as long as the top element is > the current element. Note that we don't pop an element if it is equal to the current element.
  • The maximal rectangle with the height of the popped element extends from the end of the stack element before the popped element to the start of the current element.

height = histogram[leftBars.pop()]
width = i - (leftBars[-1] + 1)
area = width*height

Consider when there is only one element in the stack besides -1 left on the stack after we have iterated through the array. Claim: There is no smaller element between -1 and the top stack element. If there were, then it implies the existence of an even smaller element between it and the top stack element. Which implies an even smaller number. And so on until we realize that 0 should be between the hypothetical element and the top stack element. But if there were a 0, it'd be on the stack before the top stack element. hence, there is no smaller element between -1 and the top stack element. The rectangle's width spans the entire histogram from 0 to the end of the array.

[darwinrlo]

Say we're given two histogram bars i and k that are adjacent on the stack with i preceding k and histogram[k] > histogram[i]. Note that histogram[k] is strictly greater than histogram[i]. Claim: All bars between i and k in the histogram are taller than k and hence taller than i.

Say there were an element j between i and k that was shorter than i. Since the bars are visited in order, j would've been visited after i and before k, which means it would've been visited after i was pushed to the stack and before k was pushed to the stack. Visiting k would've caused i to be popped off the stack, which i has not been. So clearly, such a k -- an element between i and j that is shorter than i -- cannot exist in the histogram.

...

Hence the conclusion that all bars between i and j are taller than j.