LeetCode_单调栈_困难_85.最大矩形

r囧r小猫 2023-10-06 19:11 68阅读 0赞

#### 目录 ####

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

## 1.题目 ##

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

**示例 1：**

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

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

**示例 2：**  
输入：matrix = \[\]  
输出：0

**示例 3：**  
输入：matrix = \[\[“0”\]\]  
输出：0

**示例 4：**  
输入：matrix = \[\[“1”\]\]  
输出：1

**示例 5：**  
输入：matrix = \[\[“0”,“0”\]\]  
输出：0

**提示：**  
rows == matrix.length  
cols == matrix\[0\].length  
0 <= row, cols <= 200  
matrix\[i\]\[j\] 为 ‘0’ 或 ‘1’

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

## 2.思路 ##

（1）单调栈  
在使用单调栈解决本题问题之前，需要先掌握[84.柱状图中最大的矩形][84.]这题，然后再看本题，**主要思路就是将题目中的二维数组压缩成一个一维数组，然后再调用之前上一题的方法**，具体步骤如下：  
① 定义数组 heights ，其长度为二维数组 matrix 的列数；  
② 开始遍历二维数组 matrix 的每一行，如果当前第 i 行的元素 matrix\[i\]\[j\] 为’0’，则设高度为0，即 heights\[j\] = 0；否则累加高度，即heights\[j\]++，每当一行的信息保存到 heights 之后，便开始调用方法 largestRectangleArea(int\[\] heights)，求出数组 matrix 中第 0 ~ i 行的矩形的最大面积 maxArea ；  
③ 当遍历完数组 matrix 所有的行时，最终得到的 maxArea 即为只包含 1 的最大矩形的面积。

相关题目：  
[LeetCode\_单调栈\_困难\_84.柱状图中最大的矩形][84.]

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

//思路1————单调栈
    class Solution {
        
        public int maximalRectangle(char[][] matrix) {
        
            int maxArea = 0;
            int rows = matrix.length;
            int cols = matrix[0].length;
            int[] heights = new int[cols];
            for (int i = 0; i < rows; i++) {
        
                for (int j = 0; j < cols; j++) {
        
                    if (matrix[i][j] == '0') {
        
                        //如果当前行的值为 0，则高度为 0
                        heights[j] = 0;
                    } else {
        
                        //如果当前行不是 0，则累加高度                
                        heights[j]++;
                    }
                }
                //数组 matrix 中第 0 ~ i 行最大矩形面积
                maxArea = Math.max(largestRectangleArea(heights), maxArea);
            }
            return maxArea;
        }
    
    	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;
        }
    }

[6faccda490624a78907b6f97cd94a074.png]: https://img-blog.csdnimg.cn/6faccda490624a78907b6f97cd94a074.png
[84.]: https://blog.csdn.net/weixin_43004044/article/details/120031526