题目

实现函数：输入一个长度为n的整数数组，表示n个柱的高度。求在柱状图中所能勾勒出的最大矩形面积

解决

1. 暴力法
   遍历数组，依次将当前高度作为矩形高度，向前、向后延申至边界或矮于此柱处，中间的长度为矩形的宽度。时间复杂度为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;
}

2. 使用栈
   暴力法向前、向后搜索的是比当前柱子更矮的柱，可以利用栈存储这一信息，从而只遍历一次
   若是第一个柱子，或下一个柱子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;
}