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.
本題需要使用棧維護一個高度單調(diào)遞增的序列下標(biāo)，如果遇到一個元素比當(dāng)前棧頂元素高度小，那么出棧，并計算當(dāng)前最大面積。如果棧為空，需要特殊考慮。
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 }