84. Largest Rectangle in Histogram

Apparently, for bar[i], the largest rectangle it can form depends on the number of its consecutive valid bars. Here, valid bars means those bars whose height is no less than bar[i]. So the key point is calculate the number of consecutive valid bars for each bar.

Considering the property of valid bar, we can use a monotone increasing stack to calculate it. We traverse the array to calculate the number of left and right consecutive valid bars of each bar. If the stack is not empty and the height of current bar is less than the top element in the stack. Then the top element is popped, we calculate the largest rectangle the popped bar can form and the left largest rectangle the current bar can form.

After the traverse ends, we compare the largest rectangle each bar can form and return the largest one among them.

public int largestRectangleArea(int[] heights) {
    int result[] = new int[heights.length];
    int max = 0;
    Stack<Integer> stack = new Stack<Integer>();
    for(int i = 0; i < heights.length; i++) {
	while( !stack.isEmpty() && heights[i] < heights[stack.peek()] ) {
	    int index = stack.pop();
	    result[index] += heights[index] * (i - index); // the largest rectangle of poped bar
	}
	result[i] += stack.isEmpty() ? i * heights[i] : (i - stack.peek() - 1) * heights[i]; // // the left largest rectangle of current bar
	stack.push(i);
    }
    while( !stack.isEmpty() ) {
	int index = stack.pop();
	result[index] += (heights.length - index) * heights[index]; // the right largest rectangle of bar
    }
    for(int i = 0; i < heights.length; i++) 
	max = Math.max(result[i], max);
    return max;
}