LeetCode_单调栈_困难_84.柱状图中最大的矩形

ゝ一世哀愁。 2023-10-06 19:09 41阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

**示例 1：**

![在这里插入图片描述][45d8d80235ab429aba426ee874d07204.png]

输入：heights = \[2,1,5,6,2,3\]  
输出：10  
解释：最大的矩形为图中红色区域，面积为 10

**示例 2：**

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

输入：heights = \[2,4\]  
输出：4

**提示：**  
1 <= heights.length <=105  
0 <= heights\[i\] <= 104

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

## 2.思路 ##

（1）暴力穷举法  
使用两层 for 循环穷举出所有的矩阵，然后保存最大面积并返回即可，但是该方法的时间复杂度较高，为O(n2)，所以在 LeetCode 中运行时存在超时现象，并不能通过。

（2）单调栈  
思路参考[该 LeetCode 用户题解][LeetCode]。

**所谓单调栈，即元素值单调递增或单调递减的栈**。单调栈这种数据结构，通常应用在一维数组上，**如果需要解决的问题与前后元素之间的大小关系有关的话，此时可以考虑使用单调栈**。例如在本题中，前后柱子的高度会影响最大矩形面积的计算。

相关题目：  
[LeetCode\_单调栈\_困难\_85.最大矩形][LeetCode_85.]

## 3.代码实现（Java） ##

class Solution {
        
        public int largestRectangleArea(int[] heights) {
        
            int length = heights.length;
            int maxArea = heights[0];
            int minLength;
            //暴力穷举法
            for (int i = 0; i < length; i++) {
        
                minLength = heights[i];
                for (int j = i; j < length; j++) {
        
                    //求出当前矩阵的宽
                    int width = (j > i) ? (j - i + 1) : 1;
                    //求出当前矩阵的长，它由最小的柱子高度决定
                    minLength = Math.min(heights[j], minLength);
                    //求出当前矩阵的面积
                    int curArea = width * minLength;
                    //保存当前得到的最大矩阵面积
                    maxArea = Math.max(maxArea, curArea);
                }
            }
            //返回最大面积
            return maxArea;
        }
    }

//思路2————单调栈
    class Solution {
        
        public int largestRectangleArea(int[] heights) {
        
            int length = heights.length;
            //定义最大的矩形面积，初始值为0
            int maxArea = 0;
            //定义单调栈，此处存储数组元素的下标，保证下标对应的值从栈底到栈顶逐渐递增
            Deque<Integer> stack = new ArrayDeque<>();
            for (int i = 0; i < length; i++) {
        
                //栈不为空，并且当前元素值小于等于数组下标为栈顶元素的值
                while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
        
                    //将栈顶元素出栈
                    int j = stack.pop();
                    //求左边界
                    int left = stack.isEmpty() ? 0 : stack.peek() + 1;
                    //计算以 heights[j] 为高度的最大矩形面积
                    int curArea = (i - left) * heights[j];
                    maxArea = Math.max(maxArea, curArea);
                }
                //将当前下标加入到栈中
                stack.push(i);
            }
            //求整个高度单调递增的柱子所能勾勒出来的矩形的最大面积
            while (!stack.isEmpty()) {
        
                int j = stack.pop();
                int left = stack.isEmpty() ? 0 : stack.peek() + 1;
                //此时的右边界就是数组长度
                int curArea = (length - left) * heights[j];
                maxArea = Math.max(maxArea, curArea);
            }
            return maxArea;
        }
    }
    
    //上面的代码可以再简化一下
    class Solution {
        
        public int largestRectangleArea(int[] heights) {
        
            int length = heights.length;
            int maxArea = 0;
            //定义单调栈，此处存储数组元素的下标，保证下标对应的值从栈底到栈顶逐渐递增
            Deque<Integer> stack = new ArrayDeque<>();
            for (int i = 0; i <= length; i++) {
        
                while (!stack.isEmpty() && (i == length || heights[stack.peek()] >= heights[i])) {
        
                    int j = stack.pop();
                    int left = stack.isEmpty() ? 0 : stack.peek() + 1;
                    int curArea = (i - left) * heights[j];
                    maxArea = Math.max(maxArea, curArea);
                }
                //将当前下标加入到栈中
                stack.push(i);
            }
            return maxArea;
        }
    }

[45d8d80235ab429aba426ee874d07204.png]: https://img-blog.csdnimg.cn/45d8d80235ab429aba426ee874d07204.png
[b12758c285604805af95008e2735c484.png]: https://img-blog.csdnimg.cn/b12758c285604805af95008e2735c484.png
[LeetCode]: https://leetcode.cn/problems/largest-rectangle-in-histogram/solution/84-by-ikaruga/
[LeetCode_85.]: https://blog.csdn.net/weixin_43004044/article/details/120052970