题目
实现函数：输入一个长度为n的整数数组，表示n个柱的高度。求在柱状图中所能勾勒出的最大矩形面积
解决
- 暴力法
遍历数组，依次将当前高度作为矩形高度，向前、向后延申至边界或矮于此柱处，中间的长度为矩形的宽度。时间复杂度为O(n^2)
public int maxArea(int[] heights){
int max = 0;
for (int i=0;i<heights.length;i++){
int a = i-1;
int b = i+1;
while(a!=-1 && heights[a]>=heights[i])
a --;
while(b!=heights.length && heights[b]>=heights[i])
b ++;
int height = heights[i];
int width = b-a-1;
max = Math.max(max, height*width);
}
return max;
}
- 使用栈
暴力法向前、向后搜索的是比当前柱子更矮的柱，可以利用栈存储这一信息，从而只遍历一次
若是第一个柱子，或下一个柱子i更高，则入栈；
否则栈pop，以弹出整数指向的值为高，以i-栈顶元素-1为宽，计算面积
特殊情况：pop后栈为空，表明弹出位置的柱子比之前的所有柱子矮，则宽为i
时间复杂度为O(n)，空间复杂度为O(n)。（虽然有两层循环，但内层循环代码执行的总次数最坏为n，因为每个元素最多入栈1次）
public static int maxArea2(int[] heights){
int n = heights.length;
int max = 0;
Stack<Integer> stack = new Stack<>();
for(int i=0;i<=n;i++){
//因为i指向的是“下一个”，所以i最后应该位于n处
//当i==n时，处理方式不变，则利用||来简化逻辑控制，避免出现stackEmpty异常
while(!stack.isEmpty() && (i==n || heights[i]<heights[stack.peek()])){
int height = heights[stack.pop()];
int width = stack.isEmpty()?i:i-stack.peek()-1;
max = Math.max(max,height*width);
}
//入栈应该在外层循环中
stack.push(i);
}
return max;
}
