Leetcode-084-柱状图中最大的矩形

题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

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

思路一 ： 暴力

这道问题的暴力解法比「接雨水」那道题要其实好想得多：可以枚举以每个柱形为高度的最大矩形的面积。

• 具体来说就是 ： 依次遍历柱形的高度，对于每一个高度分别向两边进行扩散，求出当前高度矩形的最大宽度。

为此，我们需要：

1. 左边看一下，看最多能向左延伸多长，找到大于等于当前柱形高度的最左边元素的下标
2. 右边看一下，看最多能向右延伸多长，找到大于等于当前柱形高度的最右边元素的下标

对于每一个位置，我们都这样操作，得到一个矩形面积，求出它们的最大值。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        // 1. 特判
        if(len == 0){
            return 0;
        }

        // 2. 依次遍历柱形的高度。对于每一个高度分别向两边进行扩散，求出以当前高度为矩形的最大宽度多少。
        int area = 0;
        for(int i = 0;i < len;i++){
            // 2.1 找到左边最后一个大于等于heights[i]的下标
            int left = i;                                           // 记录当前高度所对的索引
            int curHeight = heights[i];                             // 记录当前高度
            while(left > 0 && heights[left - 1] >= curHeight){
                left--;
            }
            // 2.2 找到右边最后一个大于等于heights[i]的下标
            int right = i;
            while(right < len - 1 && heights[right + 1] >= curHeight){
                right++;
            }

            // 2.3 面积 = 底 * 高  
            int width = right - left + 1;
            area = Math.max(area,width * curHeight);
        }

        // 3. 返回结果
        return area;
    }
}

复杂度分析

• 时间复杂度 ： O(N^2) 这里N是输入数组的长度
• 空间复杂度 ： O(1)

---

看到时间复杂度 ： O(N^2）空间复杂度 ： O(1)的组合

• 那么我们是不是可以一次遍历，不需要中心扩散就可以计算出每一个高度所对应的最大面积矩形的面积呢？
• 其实很容易想到的优化思路就是时间换空间，需要在遍历的过程中记录一些信息。

思路二 ： 单调栈

要搞清楚这个过程，请大家一定要在纸上画图，搞清楚一些细节，这样在编码的过程中就不容易出错了。

需要记录什么信息呢？

• 记录高度是不是可以呢？其实记录高度是不够的，因为还要计算宽度，很容易知道宽度是由下标确定的，记录了下标其实对应的高度就可以直接从输入数组中得出，因此，应该记录的是下标。

举例子

• 我们就拿示例的数组 [2, 1, 5, 6, 2, 3] 为例：

1. 一开始看到的柱形高度为 2 ，这个时候以这个 2 为高度的最大面积的矩形还不能确定，我们需要继续向右遍历，如下图。

2. 然后看到了以1为高度的柱形，这个时候以这个柱形为高度的矩形的最大面积还是不知道的。但是它之前的以 2 为高度的最大面积的矩形是可以确定的，这是因为这个 1 比 2 小 ，因为这个 1 卡在了这里 2 不能再向右边扩展了，如下图。

那么我们可以计算一下 以 2 为高度的最大矩形的面积是2，其实这个时候，求解这个问题的思路其实已经慢慢打开了。如果已经确定了一个柱形的高度，我们可以无视它，将它以虚框表示

3. 遍历到高度为 5 的柱形，同样的以当前看到柱形为高度的矩形的最大面积也是不知道的，因为我们还要看右边高度的情况。那么它的左右有没有可以确定的柱形呢？
   • 没有，这是因为 5 比 1 大，我们看后面马上就出现了 6，不管是 1 这个柱形还是 5 这个柱形，都还可以向右边扩展；

4. 接下来，遍历到高度为 6 的柱形，同样的，以柱形 1、5、6 为高度的最大矩形面积还是不能确定下来；

5. 再接下来，遍历到高度为 2 的柱形。

结果 ：

1. 发现了一件很神奇的事情，高度为 6 的柱形对应的最大矩形的面积的宽度可以确定下来，它就是夹在高度为 5 的柱形和高度为 2 的柱形之间的距离，它的高度是 6，宽度是 1。

将可以确定的柱形设置为虚线。

2. 接下来柱形 5 对应的最大面积的矩形的宽度也可以确定下来，它是夹在高度为 1 和高度为 2 的两个柱形之间的距离 ： 2 ，3 ；

确定好以后，我们将它标成虚线。

结论：

• 我们发现了，只要是遇到了当前柱形的高度比它上一个柱形的高度严格小的时候，一定可以确定它之前的某些柱形的最大宽度，并且确定的柱形宽度的顺序是从右边向左边。

• 这个现象告诉我们，在遍历的时候需要记录的信息就是遍历到的柱形的下标，它一左一右的两个柱形的下标的差就是这个面积最大的矩形对应的最大宽度。

• 这个时候，还需要考虑的一个细节是，在确定一个柱形的面积的时候，除了右边要比当前严格小，其实还蕴含了一个条件，那就是左边也要比当前高度严格小。

• 那如果是左边的高度和自己相等怎么办呢？我们想一想，我们之前是只要比当前严格小，我们才可以确定一些柱形的最大宽度。只要是大于或者等于之前看到的那一个柱形的高度的时候，其实都不能确定。

• 因此我们确定当前柱形对应的宽度的左边界的时候，往回头看的时候，一定要找到第一个严格小于我们要确定的那个柱形的高度的下标。这个时候 中间那些相等的柱形其实就可以当做不存在一样。因为它对应的最大矩形和它对应的最大矩形其实是一样的。

---

说到这里，其实我们的思路已经慢慢清晰了。

• 我们在遍历的时候，需要记录的是下标，如果当前的高度比它之前的高度严格小于的时候，就可以直接确定之前的那个高的柱形的最大矩形的面积，

• 为了确定这个最大矩形的左边界，我们还要找到第一个严格小于它的高度的矩形，向左回退的时候，其实就可以当中间这些柱形不存在一样。

  • 这是因为我们就是想确定 6 的宽度，6 的宽度确定完了，其实我们就不需要它了，这个 5 的高度和这个 5 的高度确定完了，我们也不需要它了。

• 我们在缓存数据的时候，是从左向右缓存的，我们计算出一个结果的顺序是从右向左的，并且计算完成以后我们就不再需要了，符合后进先出的特点。因此，我们需要的这个作为缓存的数据结构就是栈。

• 当确定了一个柱形的高度的时候，我们就将它从栈顶移出，所有的柱形在栈中进栈一次，出栈一次，一开始栈为空，最后也一定要让栈为空，表示这个高度数组里所有的元素都考虑完了。

6、最后遍历到最后一个柱形，即高度为 3 的柱形。

（一次遍历完成以后。接下来考虑栈里的元素全部出栈。）

接下来我们就要依次考虑还在栈里的柱形的高度

1. 和刚才的方法一样，只不过这个时候右边没有比它高度还小的柱形了，这个时候计算宽度应该假设最右边还有一个下标为 len （这里等于 6） 的高度为 0 （或者 0.5，只要比 1 小）的柱形。

2. 下标为 5 ，即高度为 3 的柱形，左边的下标是 4 ，右边的下标是 6 ，因此宽度是 6 - 4 - 1 = 1（两边都不算，只算中间的距离，所以减 1）；算完以后，将它标为虚线。

3. 下标为 4 ，高度为 2 的柱形，左边的下标是 1 ，右边的下标是 6 ，因此宽度是 6 - 1 - 1 = 4；算完以后，将它标为虚线。

4. 最后看下标为 1，高度为 1 的矩形，它的左边和右边其实都没有元素了，它就是整个柱形数组里高度最低的柱形，计算它的宽度，就是整个柱形数组的长度。

到此为止，所有的柱形高度对应的最大矩形的面积就都计算出来了。

这个算法经过一次遍历，在每一次计算最大宽度的时候，没有去遍历，而是使用了栈里存放的下标信息，以 O(1)的时间复杂度计算最大宽度。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        // 1. 特判
        if(len == 0){
            return 0;
        }
        if(len == 1){
            return heights[0];
        }

        // 2. 初始化
        int area = 0;
        Deque<Integer> stack = new ArrayDeque<>();

        // 3. 遍历数组元素
        for(int i = 0;i < len;i++){
            // 3.1 while 很关键，因为有可能计算出不止一个柱形的最大宽度
            while(!stack.isEmpty() && heights[i] < heights[stack.peekLast()]){              // 对应于严格小于的情况
                int curHeight = heights[stack.pollLast()];
                while(!stack.isEmpty() && heights[stack.peekLast()] == curHeight){          // 对应于左边相邻相等的情况
                    stack.pollLast();                                                       // 忽视左边相等高度的柱形
                }

                // 3.2 计算宽度
                int curWidth;
                if(stack.isEmpty()){
                    curWidth = i;
                }else{
                    curWidth = i - stack.peekLast() - 1;
                }
                // 3.3 面积
                area = Math.max(area,curHeight * curWidth);
            }
            stack.addLast(i);                                                             // 记录下标
        }

        // 4. 处理栈中剩余元素
        while (!stack.isEmpty()) {
            // 4.1 计算高度
            int curHeight = heights[stack.pollLast()];
            while (!stack.isEmpty() && heights[stack.peekLast()] == curHeight) {
                stack.pollLast();
            }
            // 4.2 计算宽度
            int curWidth;
            if (stack.isEmpty()) {
                curWidth = len;
            } else {
                curWidth = len - stack.peekLast() - 1;
            }
            // 4.3 计算面积
            area = Math.max(area, curHeight * curWidth);
        }
        return area;
    }
}

复杂度分析

• 时间复杂度 ： O(N) ，输入数组中每个元素入栈一次，出栈一次
• 空间复杂度 ： O(N) 栈最多存放的元素是数组的长度

思路三 ：单调栈 + 哨兵

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/

打赏