The current algorithm that using stack to solve this problem seems lacking some test cases. The code below is the one passed OJ, but I do think there is a test case that this code cannot pass.

The test case is [3,1,3,4,2,3], it is easily to see the max area is 8, which cover the last 4 histograms with height 2, but I do not think the algorithm will return the correct answer.

Here is the code in java:

public class Solution {

// O(n) using one stack

public int largestRectangleArea(int[] height) {

// Start typing your Java solution below

// DO NOT write main() function

int area = 0;

java.util.Stack<Integer> stack = new java.util.Stack<Integer>();

for (int i = 0; i < height.length; i++) {

if (stack.empty() || height[stack.peek()] < height[i]) {

stack.push(i);

} else {

int start = stack.pop();

int width = stack.empty() ? i : i - stack.peek() - 1;

area = Math.max(area, height[start] * width);

i--;

}

}

while (!stack.empty()) {

int start = stack.pop();

int width = stack.empty() ? height.length : height.length - stack.peek() - 1;

area = Math.max(area, height[start] * width);

}

return area;

}

}