Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given height = [2,1,5,6,2,3],
return 10.
本题需要使用栈维护一个高度单调递增的序列下标，如果遇到一个元素比当前栈顶元素高度小，那么出栈，并计算当前最大面积。如果栈为空，需要特殊考虑。
1 public class LargestRectangleinHistogram {
2 public int largestRectangleArea(int[] height) {
3 Stack<Integer> stack = new Stack<Integer>();
4 int i = 0;
5 int maxArea = 0;
6 int[] h = new int[height.length + 1];
7 h = Arrays.copyOf(height, height.length + 1);
8 while (i < h.length) {
9 if (stack.isEmpty() || h[stack.peek()] <= h[i]) {
10 stack.push(i++);
11 } else {
12 int t = stack.pop();
13 maxArea = Math.max(maxArea, h[t] * (stack.isEmpty() ? i : i - stack.peek() - 1));
14 }
15 }
16 return maxArea;
17 }
18 }