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 heights = [2,1,5,6,2,3],
return 10.
思路
對于一個bar x，計算以x為最低點的面積最大的矩形，把全部bar都計算一遍，就可以找到柱狀圖中面積最大的矩形。
如何找到以x為最低點的矩形？我們需要知道x左右兩側(cè)，第一個比x低的bar的位置，分別記做left index和right index。
從左至右遍歷所有的bar，用棧來維護(hù)這些bar。保證棧中的bar是遞增，即新遇到的bar比棧頂元素低的時候，就彈出棧頂元素。當(dāng)一個bar彈出棧的時候，這個bar就是x，新遇到的bar的坐標(biāo)就是right index，棧中上一個元素坐標(biāo)就是left index：
- 創(chuàng)建一個空棧
- 從第一個bar開始掃描
- 如果?？栈蛘?code>height[i] >= 棧頂元素高度，則將
i(下標(biāo))壓入棧中 - 如果
height[i] < 棧頂高度，不斷彈出棧頂元素，直到height[i] >= 棧頂元素高度或?？?/code>。- 令彈出棧的的元素高度是height[tp],計算以height[tp]為最低點的矩形面積。
- 對于height[tp]這個bar，left index是棧中前一個元素，right index是i。
- 由于每個Bar入棧出棧各一次，因此總時間復(fù)雜度為O(N)。
具體實現(xiàn)時，再尾部加入height = 0的bar，確保之前所有bar都能出棧
class Solution {
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) return 0;
Stack<Integer> stack = new Stack<Integer>();
List<Integer> newHeights = new ArrayList<Integer>(heights.length);
for (int i = 0; i < heights.length; i++) {
newHeights.add(Integer.valueOf(heights[i]));
}
newHeights.add(0);
int start = 0;
int end = newHeights.size();
int maxArea = 0;
for(int i = 0; i < end; i++) {
int rightIndex = 0;
int leftIndex = 0;
while (!stack.isEmpty() && newHeights.get(stack.peek()) >= newHeights.get(i)) {
int tempHeight = stack.peek();
stack.pop();
rightIndex = i;
leftIndex = stack.isEmpty() ? -1 : stack.peek();
maxArea = Math.max(maxArea, (rightIndex - leftIndex - 1) * newHeights.get(tempHeight));
}
stack.push(i);
}
return maxArea;
}
}
