/**

public int largestRectangleArea(int[] height) {

int len = height.length;

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

int maxArea = 0;

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

int h = (i == len ? 0 : height[i]);

if(s.isEmpty() || h >= height[s.peek()]){

s.push(i);

}else{

int tp = s.pop();

maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));

i--;

}

}

return maxArea;

}

/**

public int largestRectangleArea2(int[] height) {

if (height == null || height.length == 0) {

return 0;

}

int[] lessFromLeft = new int[height.length]; // idx of the first bar the left that is lower than current

int[] lessFromRight = new int[height.length]; // idx of the first bar the right that is lower than current

lessFromRight[height.length - 1] = height.length;

lessFromLeft[0] = -1;

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

int p = i - 1;

while (p >= 0 && height[p] >= height[i]) {

p = lessFromLeft[p];

}

lessFromLeft[i] = p;

}

for (int i = height.length - 2; i >= 0; i--) {

int p = i + 1;

while (p < height.length && height[p] >= height[i]) {

p = lessFromRight[p];

}

lessFromRight[i] = p;

}

int maxArea = 0;

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

maxArea = Math.max(maxArea, height[i] * (lessFromRight[i] - lessFromLeft[i] - 1));

}

return maxArea;

}

/**

public int largestRectangleArea3(int[] height) {

if (height==null) return 0;//Should throw exception

if (height.length==0) return 0;

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

index.push(-1);

int max=0;

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

//Start calculate the max value

while (index.peek()>-1)

if (height[index.peek()]>height[i]){

int top=index.pop();

max=Math.max(max,height[top]*(i-1-index.peek()));

}else break;

index.push(i);

}

while(index.peek()!=-1){

int top=index.pop();

max=Math.max(max,height[top]*(height.length-1-index.peek()));

}

return max;

}

/**

public int largestRectangleArea4(int[] heights) {

if (heights == null || heights.length == 0) return 0;

return getMax(heights, 0, heights.length);

}

private int getMax(int[] heights, int s, int e) {

if (s + 1 >= e) return heights[s];

int min = s;

boolean sorted = true;

for (int i = s; i < e; i++) {

if (i > s && heights[i] < heights[i - 1]) sorted = false;

if (heights[min] > heights[i]) min = i;

}

if (sorted) {

int max = 0;

for (int i = s; i < e; i++) {

max = Math.max(max, heights[i] * (e - i));

}

return max;

}

int left = (min > s) ? getMax(heights, s, min) : 0;

int right = (min < e - 1) ? getMax(heights, min + 1, e) : 0;

return Math.max(Math.max(left, right), (e - s) * heights[min]);

}