Q:给定一个直方图，这里盗一下图，http://blog.csdn.net/nisxiya/article/details/46562951，
例如
20150619153844882.jpg
的最大面积为10
烦烦烦.jpg
A：关键在于单调栈的运用，单调栈可以找到每个元素左右两边离他最近的比他小（或者大）的数。
import java.util.*;
import java.io.*;
public class 最大直方图面积 {
public static void main(String[] args) throws Exception{
Scanner scanner=new Scanner(System.in);
int length = scanner.nextInt();
int[] arr = new int[length];
for (int i = 0; i < length; i++) {
arr[i] = scanner.nextInt();
}
long maxArea = getMaxArea(arr);
System.out.println(maxArea);
}
public static long getMaxArea(int[] arr) {
long max = 0;
int[] temp = new int[arr.length];
Stack<Integer> stack = new Stack<>();
int preIndex;
for (int i = 0; i < arr.length; i++) {
while (!stack.isEmpty() && (arr[i] < arr[stack.peek()])) {
preIndex = stack.pop();
if(stack.isEmpty()){
temp[preIndex] = i -preIndex;
}else{
temp[preIndex] = i - stack.peek()-1;
}
}
stack.push(i);
}
int end=arr.length-1;
while(!stack.isEmpty()){
preIndex = stack.pop();
if(stack.isEmpty()){
temp[preIndex] = 1;
}else{
temp[preIndex] = end - stack.peek();
}
}
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i] * temp[i]);
}
return max;
}
}
