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

1.题目

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

示例 1：

输入：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.柱状图中最大的矩形这题，然后再看本题，主要思路就是将题目中的二维数组压缩成一个一维数组，然后再调用之前上一题的方法，具体步骤如下：
① 定义数组 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.柱状图中最大的矩形

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41