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.
Example：
Input: [2,1,5,6,2,3]
Output: 10
解釋下題目：
給定一個(gè)數(shù)組，找出其中所能包含最大的矩形的面積
1. 遍歷求解
實(shí)際耗時(shí)：500ms
public int largestRectangleArea(int[] heights) {
if (heights.length == 0 || heights == null) {
return 0;
}
int maxArea = heights[0];
int[] left = new int[heights.length];
int[] right = new int[heights.length];
//0左邊的是-1
left[0] = -1;
//最右邊的那根柱子的右邊就是數(shù)組的長度
left[heights.length - 1] = heights.length;
//為每一個(gè)柱子找到它左邊的離它最近的比它短的柱子
for (int i = 1; i < heights.length; i++) {
int j = i - 1;
while (j >= 0 && heights[j] >= heights[i]) {
j--;
}
left[i] = j;
}
//為每一個(gè)柱子找到它右邊的離它最近的比它短的柱子
for (int i = heights.length - 1; i >= 0; i--) {
int j = i + 1;
while (j < heights.length && heights[j] >= heights[i]) {
j++;
}
right[i] = j;
}
//此時(shí)已經(jīng)算出來每條柱子最左邊和最右邊的了
//System.out.println(Arrays.toString(left));
//System.out.println(Arrays.toString(right));
//計(jì)算面積
for (int i = 0; i < heights.length; i++) {
maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] - 1));
}
return maxArea;
}
踩過的坑：[0,9] 和 [2,3]
??思路：從一開始我想的是把這個(gè)分解成子問題求解，也就是我想知道一個(gè)數(shù)組最大的面積，我首先需要知道這個(gè)數(shù)組刪去最后一個(gè)元素的最大面積，然后最后把這個(gè)刪去的元素加入進(jìn)行判斷。后來發(fā)現(xiàn)有點(diǎn)復(fù)雜，之后從接雨水這道題目獲得啟示，最大的面積中，必定是包含一條柱子的，那么我針對(duì)每一條柱子，只需要求出包含這個(gè)柱子所能得到的最大解，然后從nums.length個(gè)解中找出最大的即可。
時(shí)間復(fù)雜度O(n^2)
空間復(fù)雜度O(2n)
2. 利用堆棧
實(shí)際耗時(shí)：20ms
public int largestRectangleArea2(int[] heights) {
int len = heights.length;
int maxArea = 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i <= len; ) {
int h = (i == len ? 0 : heights[i]);
//如果一直是增加的，不必計(jì)算最大值，只有在遇到下降的時(shí)候才計(jì)算
if (stack.isEmpty() || h >= heights[stack.peek()]) {
stack.push(i);
i++;
} else {
int curHeight = heights[stack.pop()];
int rightBoundary = i - 1;
//這一步其實(shí)是多次計(jì)算
int leftBoundary = stack.isEmpty() ? 0 : stack.peek() + 1;
int width = rightBoundary - leftBoundary + 1;
maxArea = Math.max(maxArea, (curHeight * width));
}
}
return maxArea;
}
??思路：整個(gè)區(qū)域可以分成若干個(gè)遞增的區(qū)塊，在每個(gè)區(qū)塊中從左到右都是逐步增大的，而最大的塊肯定在這里取到。
