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.
题意：有一个用数组表示的树状图，找出这个树状图中最大的矩形。
思路：自己想到的就是比较暴力的解法，尝试每个可能的矩形面积，找出最大的。这里面有一个优化可以做到n方时间复杂度，就是尝试每个起点时，用一个变量记录到当前终点位置，当前最小的高度是多少。
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;
}
想不出来线性的解法，看了答案，答案的思路是用栈维护一个递增序列，一旦碰到了一个小于栈顶的新元素，就知道了以当前栈顶元素高度为终点的最大矩形是多少了。
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;
}