Problem:
Solve:
主要思想：用一个栈来保存高度的索引，当当前索引的高度比前一个大的时候就加入栈中，当比它小时，就从栈中不断的弹出索引，计算最大矩形的值，直到当前索引的高度比栈顶索引高度大时停止，并把当前索引加入到栈中。
[Java Code]
public int largestRectangleArea(int[] height) {
Stack<Integer> stack = new Stack<Integer>();
int n = height.length, area = 0;
for (int i = 0; i < n; i++) {
while (!stack.empty() && height[stack.peek()] > height[i]) {
int h = height[stack.peek()];
stack.pop();
int l = stack.empty() ? -1 : stack.peek();
area = Math.max(area, h * (i - l - 1));
}
stack.push(i);
}
while (!stack.empty() && height[stack.peek()] > 0) {
int h = height[stack.peek()];
stack.pop();
int l = stack.empty() ? -1 : stack.peek();
area = Math.max(area, h * (height.length - 1 - l));
}
return area;
}
近期评论