84.柱状图中最大的矩形

小咪咪 2024-02-25 04:25 85阅读 0赞

#### 84.柱状图中最大的矩形 ####

*  题干分析
 *  解题思路
 *   *  双指针解法
     *  单调栈
 *  代码实现

## 题干分析 ##

[力扣入口][Link 1]

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

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

![在这里插入图片描述][e33f265f0b8445ce9b73ad365bbfc501.png]  
![在这里插入图片描述][e93cae2ef5e042cd84c8724d9dc09e7e.png]

*  1 <= heights.length <=10^5
 *  0 <= heights\[i\] <= 10^4

## 解题思路 ##

本题和**42. 接雨水**，是遥相呼应的两道题目，建议都要仔细做一做，原理上有很多相同的地方，但细节上又有差异，更可以加深对单调栈的理解！

其实这两道题目先做那一道都可以，但我先写的**42.接雨水**的题解，所以如果没做过接雨水的话，建议先做一做接雨水，可以参考我的题解：**42. 接雨水**

暴力法不能通过leetcode，超时了。

### 双指针解法 ###

本题双指针的写法整体思路和**42. 接雨水**是一致的，但要比42. 接雨水难一些。

难就难在本题要记录记录每个柱子 左边第一个小于该柱子的下标，而不是左边第一个小于该柱子的高度。

所以需要循环查找，也就是下面在寻找的过程中使用了while，详细请看下面注释，整理思路在题解：**42. 接雨水**中已经介绍了。

### 单调栈 ###

本地单调栈的解法和接雨水的题目是遥相呼应的。

为什么这么说呢，**42. 接雨水**是找每个柱子左右两边第一个大于该柱子高度的柱子，而本题是找每个柱子左右两边第一个小于该柱子的柱子。

**这里就涉及到了单调栈很重要的性质，就是单调栈里的顺序，是从小到大还是从大到小。**

在题解**42. 接雨水** 中我讲解了接雨水的单调栈从栈头（元素从栈头弹出）到栈底的顺序应该是从小到大的顺序。

那么因为本题是要找每个柱子左右两边第一个小于该柱子的柱子，所以从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序！

我来举一个例子，如图：  
![在这里插入图片描述][2a759148aa5a45b0a0e67ad9fe7695da.png]  
只有栈里从大到小的顺序，才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。

所以本题单调栈的顺序正好与接雨水反过来。

此时大家应该可以发现其实就是**栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度**

理解这一点，对单调栈就掌握的比较到位了。

除了栈内元素顺序和接雨水不同，剩下的逻辑就都差不多了，在题解**42. 接雨水** 我已经对单调栈的各个方面做了详细讲解，这里就不赘述了。

主要就是分析清楚如下三种情况：

*  情况一：当前遍历的元素heights\[i\]大于栈顶元素heights\[st.top()\]的情况
 *  情况二：当前遍历的元素heights\[i\]等于栈顶元素heights\[st.top()\]的情况
 *  情况三：当前遍历的元素heights\[i\]小于栈顶元素heights\[st.top()\]的情况

**在height数组前后需要加元素0。**

如果数组本身就是升序的，例如\[2,4,6,8\]，那么入栈之后 都是单调递减，一直都没有走 情况三 计算结果的哪一步，所以最后输出的就是0了。 如图：  
![在这里插入图片描述][edacbd9542f949618e1392e85c173ac4.png]  
那么结尾加一个0，就会让栈里的所有元素，走到情况三的逻辑。

开头为什么要加元素0？

如果数组本身是降序的，例如 \[8,6,4,2\]，在 8 入栈后，6 开始与8 进行比较，此时我们得到 mid（8），rigt（6），但是得不到 left。

（mid、left，right 都是对应版本一里的逻辑）

因为 将 8 弹出之后，栈里没有元素了，那么为了避免空栈取值，直接跳过了计算结果的逻辑。

之后又将6 加入栈（此时8已经弹出了），然后 就是 4 与 栈口元素 8 进行比较，周而复始，那么计算的最后结果resutl就是0。 如图所示：  
![在这里插入图片描述][4e8615385d714c5691c45a83b7cd202c.png]  
所以我们需要在height数组前后各加一个元素0。

## 代码实现 ##

class Solution {
        
        // 84.柱状图中最大的矩形
        public int largestRectangleArea(int[] heights){
        
            Stack<Integer> st = new Stack<Integer>();
    
            // 数组扩容, 在头和尾各加入一个元素
            int[] newHeights = new int[heights.length + 2];
            newHeights[0] = 0;
            newHeights[newHeights.length - 1] = 0;
            for(int index = 0; index < heights.length; index++){
        
                newHeights[index + 1] = heights[index];
            }
            heights = newHeights;
            st.push(0);
            int result = 0;
            // 第一个元素已经入栈，从下标1开始
            for(int i = 1; i < heights.length; i++){
        
                // 注意heights[i] 是和heights[st.top()] 比较 ，st.top()是下标
                if (heights[i] > heights[st.peek()]) {
        
                    st.push(i);
                } else if(heights[i] == heights[st.peek()]){
        
                    st.pop(); // 这个可以加，可以不加，效果一样，思路不同
                    st.push(i);
                } else{
        
                    while(heights[i] < heights[st.peek()]){
         // 注意是while
                        int mid = st.peek();
                        st.pop();
                        int left = st.peek();
                        int right = i;
                        int w = right - left - 1;
                        int h = heights[mid];
                        result = Math.max(result, w * h);
                    }
                    st.push(i);
                }
            }
            return result;
        }
    }

**参考资料**：[代码随想录-84.柱状图中最大的矩形][-84.]

[Link 1]: https://leetcode.cn/problems/largest-rectangle-in-histogram/
[e33f265f0b8445ce9b73ad365bbfc501.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/e7561753a8b246c2994b5c51cecdbbf0.png
[e93cae2ef5e042cd84c8724d9dc09e7e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/b4380e430e22478c81c12690bf6cab72.png
[2a759148aa5a45b0a0e67ad9fe7695da.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/08e2deef3f444217b1b361ea17760bfd.png
[edacbd9542f949618e1392e85c173ac4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/b964eaf7cbfd4733ab5c5ee5db045954.png
[4e8615385d714c5691c45a83b7cd202c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/496e563f220a46ecb82114541af27839.png
[-84.]: https://programmercarl.com/0084.%E6%9F%B1%E7%8A%B6%E5%9B%BE%E4%B8%AD%E6%9C%80%E5%A4%A7%E7%9A%84%E7%9F%A9%E5%BD%A2.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE