Largest rectangle in histogram

This is a very common problem asked in interviews of top tier companies. Most efficient solution to this problem is to build a stack of the bars in increasing order of height. For any bar, the width of the rectangle with it as height is equal to the number of bars in between the immediate smaller bars on either side.

Consider the bar with height 5 in the provided example, the immediate smaller bars on either side are 4 and 1. The number of bars in between these two smaller bars is 2 and so area of the rectangle formed will be 10 (5X2). As you continue to traverse the histogram, you will find that the bar with height 7 has lower bounds 1 and 2 which gives a width of 3. This happens to be the largest rectangle in terms of area (7X3=21) which can be fitted into the histogram.

public int findLargestRectangleInHistogram(int[] heights){
    int maxArea = 0;
    Deque<Integer> stack = new LinkedList<>();
    //Return 0 if input array is empty
    if(heights == null || heights.length == 0) return maxArea;
    for(int i = 0; i <= heights.length; ++i){
        //Set h to height of current element or zero if we have reached end of array
        int h = (i == heights.length ? 0 : heights[i]);
        //Check if stack is empty or height of current element is greater than element on top of stack
        if(stack.isEmpty() || h >= heights[stack.peek()]){
            //Push current element to stack. The previous top is the lower bound for rectangle with height of current element.
            stack.push(i);
        }
        else{
            //Current element is upper bound for rectangle formed with current top of the stack as height
            int ind = stack.pop();
            //Calculate area using the lower and upper bounds for bar with index ind
            maxArea = Math.max(maxArea, heights[ind]*(stack.isEmpty()? i: i - 1 - stack.peek()));
            --i;
        }
    }
    return maxArea;
}

Execute solution @jdoodle