【单调栈】代码随想录算法训练营第六十天 |84.柱状图中最大的矩形（待补充）

迈不过友情╰ 2024-04-23 04:44 69阅读 0赞

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

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode]

2、文章讲解：[代码随想录][Link 1]

3、题目：

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

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

![67fbca7bef4e116416f2ba62d05bb899.png][]

![90eea29a128d3893a69d6fedddaa734b.png][]

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

4、视频链接：

[单调栈，又一次经典来袭！ LeetCode：84.柱状图中最大的矩形\_哔哩哔哩\_bilibili][LeetCode_84._bilibili]

int[] newHeight = new int[heights.length + 2];
            System.arraycopy(heights, 0, newHeight, 1, heights.length);
            newHeight[heights.length+1] = 0;
            newHeight[0] = 0;
    
            Stack<Integer> stack = new Stack<>();
            stack.push(0);
    
            int res = 0;
            for (int i = 1; i < newHeight.length; i++) {
                while (newHeight[i] < newHeight[stack.peek()]) {
                    int mid = stack.pop();
                    int w = i - stack.peek() - 1;
                    int h = newHeight[mid];
                    res = Math.max(res, w * h);
                }
                stack.push(i);
    
            }
            return res;

##  ##

[. - _LeetCode]: https://leetcode.cn/problems/largest-rectangle-in-histogram/
[Link 1]: 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
[67fbca7bef4e116416f2ba62d05bb899.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/3ca46737349e4acd9d8dac8dcf33f635.png
[90eea29a128d3893a69d6fedddaa734b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/52d1baa4968a46cdac9fcfa7bbf06603.png
[LeetCode_84._bilibili]: https://www.bilibili.com/video/BV1Ns4y1o7uB/