算法：Leetcode 84最大柱状图

题意

给出一组数组，代表一个柱状图，求出柱状图的最大矩形面积

思路

思考怎么才能求出一个柱状图的最大矩形？

image.png

例如：传入的是 2 1 5 6 2 3的一个数组
我们去求她的最大矩形。从直观来说 就是把每一个数组拉平，然后计算面积，比较得出最大值嘛
比如：遍历第一个元素2，她拉平只能到自己，因为下一个元素是1，肯定拉不了。现在面积为2
在下一个元数为1，拉平他，这时候就很特例了，它可以往左边拉，也可以往右边拉。
左边拉到下标2的位置，右边可以拉到数组末尾。
所以它的面积 应该是 （右边界 - 左边界 ）* 1，我们找到了一个解决方案了。
方法一、暴力法
对于每一个元素都去寻找左右界，然后求出面积最大值
时间复杂度o(n *n),查找效率不高。

方法二
我们思考如果这个数组是递增的
比如1 2 3 4，对于任何它的右边界就是数组的末尾，左边界就是前一个数的位置！
我们动态的维护这么一个集合来对每个元素的边界进行查找，然后 （右边界 - 左边界 ）* 元素 得到面积最大值。得到下面代码

    public int largestRectangleArea(int[] heights) {
        if (heights==null || heights.length == 0)
            return 0;
        if (heights.length == 1)
            return heights[0];
        //首先要维护一个元素位置i的左右边界
        int [] left = new int [heights.length];
        int [] right = new int[heights.length];
        //需要维护一个递增序列使用栈来做
        Stack<Integer> stack = new Stack<>();
        //假设每一个右边界都是数组的末尾
        for (int i = 0; i < right.length; i++) {
            right[i] = heights.length;
        }
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty()&& heights[stack.peek()] > heights[i]){
                right[stack.pop()] = i;
            }
            //找到最左边的位置了
            left[i] = stack.isEmpty()?-1:stack.peek();
            //加入栈
            stack.push(i);
        }
        //开始计算最大值了
        int max = 0;
        for (int i = 0; i < heights.length; i++) {
            max = Math.max((right[i] - left[i]-1) * heights[i],max);

        }
        return max;
    }

时间复杂度平均的情况为o(n)