力扣84-柱状图中最大的矩形

一、原题题目

1.1 题目

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上左图是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。右图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

1.2 示例

示例：

输入： [2,1,5,6,2,3]
输出： 10

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

二、解题思路

2.1 【暴力】思路解题

解题思路

读完题目没有想到这个题算是什么类型的题，但自己有一个解题思路：遍历数组的每一个元素，确定其左右比它高的元素个数和，包含它自己作为以它为参考中心的能勾勒出的矩形的宽，以它的值为高去计算面积。与最大面积值比较是否取代最大面积值。

详细代码（Java）

public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length==0)   return 0;   // 数组为空返回0
        int len = heights.length;       // 记录长度
        int max = heights[0];           // 开始把最大面积定位heights[0]
        for (int i = 0;i<len;i++){      // 遍历每一个元素
            int left = i,right = i;     // 定义开始小于自己的左右边界，开始都等于自己
            while (left>=0&&heights[left]>=heights[i])  left--;     // 往左边去找小于自己的左边界
            while (right<len&&heights[right]>=heights[i])   right++;// 往右边去找小于自己的右边界
            max = Math.max(max,(right-left-1)*heights[i]);  // 此时的宽为 right - left -1
        }
        return max;
    }

性能分析

时间复杂度：O(N²)，这里 N 是输入数组的长度。
空间复杂度：O(1)。
代码执行结果

虽然是通过了，但时间和空间上性能都不是很好。看了相关题解介绍后才知道自己想的这种是暴力解法，之所以效率低，是因为每考虑过一个位置后没有为后面的计算提供相关信息简化后面的运算。

2.1 【栈】思路解题

解题思路

上述的暴力解法每次遍历的时候没有记录相关的信息给后面的计算提供帮助，所以效率比较低，但是读了官方题解之后其实感觉还是不是很明白，左思右想后大概应该是这么个思路过程。

我们在暴力解法中，需要不断的向左右去找严格比当前值小的下标，然后计算宽度。左边是我们已经遍历过的数据，但是没能保存住最下值的下标（需要优化的地方），右边的最小值还是需要继续遍历去找到。这里我直接在参考的题解上得出下面利用栈的过程：其实就是两种情况：

当前位置的值（高度）大于栈顶位置的值（高度）时，当前位置的下标入栈：因为后面的位置高度比栈顶位置的高度大，及还没找到比它小的右边界，所以入栈先不能计算栈顶元素位置的最大矩形。
当前位置的值（高度）小于栈顶位置的值（高度）时，记下当前位置下标即是栈顶元素的右边界，说明栈顶元素就可以求出最大矩形，则出栈，对应值作为高度，再找到左边比它小的左边界即可，如果栈不为空即新的栈顶位置就是左边界，栈为空则左边界一直可以到第一个元素，即下标为0，为了计算统一，我们定这种情况的左边界为-1。

下面以示例 [2,1,5,6,2,3] 一步一步演示过程：

经过上述步骤后最后 Smax 即保存的最大矩形面积。

详细代码（Java）

public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length==0)   return 0;   // 数组为空返回0
        int len = heights.length;       // 记录长度
        int Smax = 0;                   // 记录最大面积
        Deque<Integer> stack = new ArrayDeque<>(len);
        for (int i =0;i<len;i++){       // 遍历每一个元素
            // 栈不为空，且当前元素小于栈顶元素，则计算栈顶元素能勾勒矩形的面积
            while (!stack.isEmpty()&&heights[i]<heights[stack.peekLast()]){
                int right = i;          // 右边界为当前下标
                int height = heights[stack.pollLast()]; // 栈顶出栈记录高度
                int left = stack.isEmpty()?-1:stack.peekLast();  // 左边界：栈不空则为栈顶元素，否则为-1
                Smax = Math.max(Smax,height*(right-left-1));    // 计算面积比较
            }
            stack.addLast(i);   // 栈顶元素不大于当前值，入栈
        }
        while (!stack.isEmpty()){   // 遍历完了数组
            int right = len;        // 右边界为数组长度
            int height = heights[stack.pollLast()]; // 栈顶出栈记录高度
            int left = stack.isEmpty()?-1:stack.peekLast(); // 左边界：栈不空则为栈顶元素，否则为-1
            Smax = Math.max(Smax,height*(right-left-1));    // 计算面积比较
        }
        return Smax;
    }