【LeetCode】柱状图中最大的矩形、最大矩形（神之转化）

梦里梦外; 2023-01-05 05:13 98阅读 0赞

## 【LeetCode】柱状图中最大的矩形、最大矩形 ##

### 柱状图中最大的矩形★★★ ###

[LeetCode84. 柱状图中最大的矩形][LeetCode84.]

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

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

![在这里插入图片描述][20210111183431780.png_pic_center]

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

![在这里插入图片描述][20210111183446896.png_pic_center]

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

【**示例**】

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

【**解题思路**】

方法一：暴力法

对于每个柱状图，以它为高的矩形的宽可由下求得：`ri - le - 1`

*  向左遍历直至`heights[le] < heights[i]`
 *  向右遍历直至`heights[ri] < heights[i]`

然后更新其面积为`area = Math.max(area, heights[i] * len)`

class Solution {
        
        public int largestRectangleArea(int[] heights) {
        
            int area = 0, n = heights.length;
            int le = 0, ri = 0;
            for(int i = 0; i < n; i++) {
        
                le = ri = i;
                while(le >= 0 && heights[le] >= heights[i]) le--;
                while(ri < n  && heights[ri] >= heights[i]) ri++;
                int len = ri - le - 1;
                area = Math.max(area, heights[i] * len);
            }
            return area;
        }
    }

方法二：单调栈

`单调递增栈`中保存对应柱状图的下标

顺序遍历数组

*  若栈不为空且`heights[i] < height[stack.peek()]`(小于栈顶元素)，则栈顶对应的柱状图的高度`h`可计算，出栈一个元素，左边边界为栈顶元素，右边边界为`heights[i]`，此时宽度为`i - stack.peek() - 1`，  
    \-更新面积为`area = Math.max(area, h * (i - stack.peek() - 1))`
 *  将下标`i`入栈

class Solution {
        
        public int largestRectangleArea(int[] heights) {
        
            int n = heights.length;
            int[] temp = new int[n + 2];
            //左右添加两个高为0的柱状图方便计算
            System.arraycopy(heights, 0, temp, 1, n);
            Stack<Integer> stack = new Stack<>();
            int area = 0;
            for(int i = 0; i < temp.length; i++) {
        
                while(!stack.isEmpty() && temp[i] < temp[stack.peek()]) {
        
                    int h = temp[stack.pop()];
                    area = Math.max(area, h * (i - stack.peek() - 1));
                }
                stack.push(i);
            }
            return area;
        }
    }

--------------------

### 最大矩形★★★ ###

[LeetCode85. 最大矩形][LeetCode85.]

【**题目**】给定一个仅包含 `0` 和 `1` 、大小为 `rows x cols` 的二维二进制矩阵，找出只包含 `1` 的最大矩形，并返回其面积。

【**示例**】

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
    输出：6
    解释：最大矩形如上图所示。

【**解题思路**】

仔细观察示例中图，可按层遍历，看其元素将其是否为1来改变柱状图的高度，初始柱状图高度都为0，对于每一层元素

*  若当前值为1，则柱体高度`加1`
 *  若当前值为0，则柱体高度`为0`

求**最大矩形**可转化为求每一层**柱状图中最大的矩形**。

class Solution {
        
        public int maximalRectangle(char[][] matrix) {
        
            if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
            int m = matrix.length, n = matrix[0].length;
            int[] heights = new int[n + 2];  //左右各添加一个高为0的柱状图
            int res = 0;
            for(int i = 0; i < m; i++) {
        
                //将每一层转化为柱状图
                for(int j = 0; j < n; j++) {
        
                    if(matrix[i][j] == '1') {
        
                        heights[j + 1] += 1;
                    }else {
        
                        heights[j + 1] = 0;
                    }
                }
                //调用柱状图中最大的矩形代码并更新最大面积
                res = Math.max(res, maxAreaRectangle(heights));
            }
            return res;
        }
        
        //柱状图中最大的矩形代码
        private int maxAreaRectangle(int[] heights) {
        
            int area = 0;
            Stack<Integer> stack = new Stack<>();
            for(int i = 0; i < heights.length; i++) {
        
                while(!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
        
                    int h = heights[stack.pop()];
                    area = Math.max(area, h * (i - stack.peek() - 1));
                }
                stack.push(i);
            }
            return area;
        }
    }

[LeetCode84.]: https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
[20210111183431780.png_pic_center]: /images/20221119/78b6da3abc50464699d4b4d99251ed6a.png
[20210111183446896.png_pic_center]: /images/20221119/e136b3159778431f9a7e3b27bb667425.png
[LeetCode85.]: https://leetcode-cn.com/problems/maximal-rectangle/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210111183515321.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw==,size_16,color_FFFFFF,t_70#pic_center