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.
題意：有一個(gè)用數(shù)組表示的樹(shù)狀圖，找出這個(gè)樹(shù)狀圖中最大的矩形。
思路：自己想到的就是比較暴力的解法，嘗試每個(gè)可能的矩形面積，找出最大的。這里面有一個(gè)優(yōu)化可以做到n方時(shí)間復(fù)雜度，就是嘗試每個(gè)起點(diǎn)時(shí)，用一個(gè)變量記錄到當(dāng)前終點(diǎn)位置，當(dāng)前最小的高度是多少。
public int largestRectangleArea(int[] heights) {
int maxarea = 0;
for (int i = 0; i < heights.length; i++) {
int minheight = Integer.MAX_VALUE;
for (int j = i; j < heights.length; j++) {
minheight = Math.min(minheight, heights[j]);
maxarea = Math.max(maxarea, minheight * (j - i + 1));
}
}
return maxarea;
}
想不出來(lái)線性的解法，看了答案，答案的思路是用棧維護(hù)一個(gè)遞增序列，一旦碰到了一個(gè)小于棧頂?shù)男略?，就知道了以?dāng)前棧頂元素高度為終點(diǎn)的最大矩形是多少了。
public int largestRectangleArea(int[] heights) {
Stack < Integer > stack = new Stack < > ();
stack.push(-1);
int maxarea = 0;
for (int i = 0; i < heights.length; ++i) {
while (stack.peek() != -1 && heights[stack.peek()] >= heights[i])
maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack.peek() - 1));
stack.push(i);
}
while (stack.peek() != -1) {
maxarea = Math.max(maxarea, heights[stack.pop()] * (heights.length - stack.peek() -1));
}
return maxarea;
}