Largest Rectangle in histogram

High Level:

Two Methods:

LeftMost rightMost:

Traverse through three times.

Find longest non-descending sequence left and right.

Calculate middle out for each tile.

Clearing the debris:

use a stack of indexes to keep track ascending sequences

rule of traversal:

while ascending, add to stack

on descend:

while top of stack is >= cur index:

1. pop the top, that's the height

2. find left bound: if the stack is empty: 0, else its the new top of the stack

3. check cur max against height * (i - left - 1)

4. add cur index to stack

class Solution {
    public int largestRectangleArea(int[] arr) {
        Deque<Integer> stack = new LinkedList<>(); //store indexes
        int result = 0;
        for(int i = 0; i <= arr.length; i++){
            int curHeight = i == arr.length ? 0 : arr[i];
            
            while(!stack.isEmpty() && arr[stack.peekFirst()] >= curHeight){
                int height = arr[stack.pollFirst()];
                int left = stack.isEmpty() ? 0 : stack.peekFirst() + 1;
                result = Math.max(result, height * (i - left));
            }
            stack.offerFirst(i);
        }
        return result;
    }
}   

Details:

WHY ASCENDING SEQUENCE?

ex: 12342

^

cur

once we pop out all heights greater or equal to cur. We are guaranteed that cur can extend until the new top index.

Why pop equal size tiles?

for cases like 2 2 1:

The first 2 needs to be popped, because the implicit left bound of each tile is tracked by the index at the top of the stack. (ref: line 10) Therefore without popping the 2 at index 0, we would get two 2x1 rectangles instead of one 2x2 rectangle.