84. Largest Rectangle in Histogram (Hard)

https://leetcode.com/problems/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.

Example:

Input: [2,1,5,6,2,3]
Output: 10

Solutions

class Solution {

    // This problem can be solved by a few lines of code. However, it is not a problem
    // that can be thought through the problem-solving process readily. The idea for this
    // problem is ingenious and pretty much like the problem 239. Sliding Window Maximum (Hard).

    // This problem is different from 11. Container With Most Water (Medium). Problem 11
    // requires to sort out the lowest boundary of the container so that we can work out the max
    // volume of it.

    // To sort out the maximum area, the brute-force solution is to go through all the possible sub
    // arrays. Then find out the lowest histogram for each range.

    // We apply a stack to keep elements that larger than stack top, which means we can always
    // get the lowest histogram of a given range. For instance, stack holds elements [2,3,6] annd
    // current position is 7, which means when we perform backtracking:

    // 1. for any histogram bars after position 6 (7 is not guarantee, only sure for processed
    // elements), the lowest is heights[6];

    // 2. for histogram bars after position 3, the lowest becomes heights[3]; You may think range
    // [4:6] and [5:6] are neglected, however, we do it intentionally. Because they are already
    // calculated, that is the reason why 4 and 5 are absent from the stack.

    // 3. a little different for position 2, it represent the lowest bar from current to 0. Because
    // position 0 and 1 should be higher then 2, otherwise they will be put into the stack.

    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }

        int len = heights.length;

        //Once the index are determined, the shadow area depends on the lowest value
        // within these two index.

        Stack<Integer> stack = new Stack<>();

        int max = 0;
        for (int i = 0; i < len; i++) {

            // if the current histogram is lower than previous one
            while (!stack.isEmpty()) {
                // Do not push in heights[i] if heights[i] < stack top because it breach
                // the ascending order. Deal with elements on the stack top until it is able to meet
                // forementioned requirements.
                if (heights[stack.peek()] < heights[i]) {
                    break;
                }

                // Is there any chance that certain pair of continuous elements in stack is discrete
                // in the histogram? The answer is yes.

                // Pop out the element that of higher histogram bar than i
                int higherHist = stack.pop();

                int width = stack.isEmpty() ? i : (i - higherHist);

                // From i (exclusive) to each element in stack, the lowest height is itself.
                int height = heights[higherHist];

                // Calculate the area of histograms from i to stack top.
                int area = width * height;

                max = Math.max(max, area);
            }

            // Elements push into stack are sorted naturally in ascending order.
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            int area = heights[stack.pop()] * (stack.isEmpty() ? len : len - stack.peek() - 1);
            max = Math.max(max, area);
        }

        return max;
    }
}

Incorrect Solutions

References