[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.

For the most naive method, we could start from one position i and expand to left and right as long as the height is height[left] >= height[i] or height[right] >= height[i]. This would give O(n^2) time complexity and would TLE. Actually, we have done many repeat work. For example, when we have check position i we calculate the furthest position it could reach to the left, then when we compute i+1, if height[i+1] <= height[i], we know for sure that i+1 could reach that point, too. We could use this to pre-calculate two array, each represent the furthest position to the left and right a given position could reach. The calculation of the array would utilize the result of the prior result so this would speed up the calculation. The amortized time complexity would be O(n).

    public int largestRectangleArea(int[] height) {
        int n = height.length;
        if(n == 0)
            return 0; // corner case
        int[] left = new int[n];
        int[] right = new int[n];
        left[0] = 0;
        for(int i = 1; i < n; i++) {
            int ind = i; 
            while(ind > 0 && height[ind - 1] >= height[i])
                ind = left[ind - 1];
            left[i] = ind;
        }
        right[n-1] = n-1;
        for(int i = n-2; i >= 0; i--) {
            int ind = i;
            while(ind < n-1 && height[ind + 1] >= height[i])
                ind = right[ind + 1];
            right[i] = ind;
        }
        int ma = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++) {
            ma = Math.max(ma, height[i]*(right[i] - left[i] + 1));
        }
        return ma;
    }

Another solution is to use a stack, the details is available here http://www.geeksforgeeks.org/largest-rectangle-under-histogram/. The key idea here is that when a shorter histogram appear after a higher one, then the higher one would be turncate by this shorter one and we do not need to keep it any more.

    public int largestRectangleArea(int[] height) {
        int n = height.length;
        if(n == 0)
            return 0; // corner case
        Stack<Integer> stack = new Stack<Integer>();
        int i = 0;
        int ma = Integer.MIN_VALUE;
        while(i < n) {
            if(stack.isEmpty() || height[i] >= height[stack.peek()]) {
                stack.push(i);
                i++;
            }
            else {
                int tmp = stack.pop();
                int area = height[tmp]*(stack.isEmpty() == true ? i : (i - stack.peek() - 1));
                ma = Math.max(ma, area);
            }
        }
        while(stack.isEmpty() == false) {
            int tmp = stack.pop();
            int area = height[tmp]*(stack.isEmpty() == true ? i : (i - stack.peek() - 1));
            ma = Math.max(ma, area);
        }
        return ma;
    }