Example: Maximum rectangle‐histogram area - rFronteddu/general_wiki GitHub Wiki

You are given an array x and tasked to find the maximum rectangular area.

Rationale:

• For each bar x, we calculate the area with x as the smallest bar in the rectangle. If we do that for each bar and find the max area our task is done.
• To calculate the area with x as the smallest bar, we need the index of the first smaller bar to the left and right.
• We traverse each element from left to right a stack of bars
• We pop a bar when we find a smaller bar. When that happens we calculate the area of the popped bar.
• After popping, the stack top is our left index and the index of the current item is our right index.
• It follows that the the current area A = x(curr) * (i - stack.top() - 1)

maxRectArea(x)
    // x[0..n]
    n = x.len
    i = 0;
    s = stack()
    maxArea = 0

    while i < n
        if s.empty() || x[i] >= x[s.top()]
            s.push(i)
            i++
        else 
            // time to calculate the area
            curr = s.pop()
            if s.empty()
                // if stack is empty, the width is until i        
                currArea = x[curr] * i
            else 
                // otherwise, width is from current to index after the new top of the stack
                currArea = x[curr] * (i - s.top() - 1)
            if currArea > maxArea
                maxArea = currArea
            
            
    // i == x.len
    while !s.empty() {
        curr = s.pop()
        if s.empty()
            currArea = x[curr] * i
        else 
            currArea = x[curr] * (i - s.top() - 1)
        if currArea > maxArea
            maxArea = currArea

    return maxArea