Leetcode: Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

Solution:

We use a stack we keep the positions of increasing height, we also have to ensure that there is no element smaller in the histogram in between.  

For instance, when we are processing the 4th element in the example the stack will be (4,3,2) and when we process the 5th element we pop two elements before pushing the processing element, becoming the stack (5, 2).

When we pop an element ($tp$)  we can calculate the maximum rectangle with the this element as height as follows: $height[tp] *  (i-stack.peek()-1)$

public class Solution {
    public int largestRectangleArea(int[] height) {
        if(height.length == 0)
            return 0;
        Deque stack = new ArrayDeque();
        
        int maxArea=0;
        int i = 0;
        while (i < height.length)
        {
            if(stack.isEmpty() || height[i] >= height[stack.peek()] )
                stack.push(i++);
            else
            {
                int tp = stack.pop();  
                
                int area = height[tp] * (stack.isEmpty() ? i : i - stack.peek() - 1);
 
                if (maxArea < area)
                    maxArea = area;
            }
        } 
        
        while (!stack.isEmpty())
        {
                int tp = stack.pop();  
                
                int area = height[tp] * (stack.isEmpty() ? i : i-1 - stack.peek());
 
                if (maxArea < area)
                    maxArea = area;
        }
 
        return maxArea;
    }
}