Largest Rectangle in Histogram

Version #2 Segment Tree [TODO]

Version #3 Stack

Time O(n) Space O(n)
49.81%
public class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        int maxArea = 0;
        //stack of index
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int left, right, curr;
        for (int index = 0; index < heights.length; index++) {
            while (!stack.isEmpty() && heights[index] < heights[stack.peek()]) {
                curr = stack.pop();
                //Empty stack means there's no element on its left lower than itself
                left = stack.isEmpty() ? -1 : stack.peek();
                right = index;
                maxArea = Math.max(maxArea, heights[curr] * (right - left - 1));
            }
            stack.push(index);
        }
        while (!stack.isEmpty()) {
            curr = stack.pop();
            left = stack.isEmpty() ? -1 : stack.peek();
            right = heights.length;
            maxArea = Math.max(maxArea, heights[curr] * (right - left - 1));
        }
        return maxArea;
    }
}


Version #1 Brute Force Algorithm
Time Limit Exceeded
Time O(n^2)
public class Solution {
    /**
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    public int largestRectangleArea(int[] height) {
        // write your code here
        if (height == null || height.length == 0) return 0;
        int left, right;
        int maxArea = 0;
        for (int curr = 0; curr < height.length; curr++) {
            left = curr;
            while (left > 0 && height[left - 1] >= height[curr]) left--;
            right = curr;
            while (right < height.length - 1 && height[right + 1] >= height[curr]) right++;
            //System.out.println(left + " " + right + " " + height[curr]);
            maxArea = Math.max(maxArea, (right - left + 1) * height[curr]);
        }
        return maxArea;
    }
}