给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

 

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

 

示例:

输入: [2,1,5,6,2,3]
输出: 10

 

思路：

维护一个递增的栈

	public static int getMaxArea(int[] heights) {
		Stack<Integer> stack = new Stack<>();
		int max = 0;
		for (int i = 0; i < heights.length; i++) {
			if (stack.isEmpty() || stack.peek() <= heights[i]) {  //栈为空或者当前值比栈顶大
				stack.push(heights[i]);
			} else {
				int count = 0;
				while (!stack.isEmpty() && stack.peek() > heights[i]) {
					count++;
					int h = stack.pop();
					max = Math.max(max, h * count);
				}
				// 用当前高度补齐之前弹出的
				while (count != 0) {
					stack.push(heights[i]);
					count--;
				}
				stack.push(heights[i]); // 当前高度入栈
			}

		}
		//和栈中的最大面积比大小
		int count=0;
		while (!stack.isEmpty()) {
			count++;
			max=Math.max(max, stack.peek()*count);
			stack.pop();
		}
		return max;
	}