☆打卡算法☆LeetCode 85、最大矩形 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定包含0和1的二维矩阵，找出只包含1的最大矩阵，返回其面积。”

题目链接：

来源：力扣（LeetCode）

链接：85. 最大矩形 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给定一个仅包含 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

二、解题

1、思路分析

这道题跟84题【柱状图中最大的矩形】很类似，不过84题是一维的，这个是二维的。

首先，说一下暴力解法：列举所有可能出现的矩形，枚举矩形所有的左上角和右下角坐标，并检查该矩形是否是面积最大的，但是这样做时间复杂度过高，会超时。我发现在学算法之前我写出来的算法都是暴利解法。。。

OK，言归正传，这道题还是可以用单调栈来解决，单调栈的特性就是如果当前元素比栈顶元素小，就加入栈，不然就将栈中的元素弹出，知道当前元素小于栈顶元素就加入。

那么就可以使用单调栈的做法，找到最高的柱子，并找到它左右的最大高度，拼接成最大的矩形，得到面积就是想要的结果。

2、代码实现

代码参考：

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].length;
        int[][] left = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }

        int ret = 0;
        for (int j = 0; j < n; j++) { // 对于每一列，使用基于柱状图的方法
            int[] up = new int[m];
            int[] down = new int[m];

            Deque<Integer> stack = new LinkedList<Integer>();
            for (int i = 0; i < m; i++) {
                while (!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]) {
                    stack.pop();
                }
                up[i] = stack.isEmpty() ? -1 : stack.peek();
                stack.push(i);
            }
            stack.clear();
            for (int i = m - 1; i >= 0; i--) {
                while (!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]) {
                    stack.pop();
                }
                down[i] = stack.isEmpty() ? m : stack.peek();
                stack.push(i);
            }

            for (int i = 0; i < m; i++) {
                int height = down[i] - up[i] - 1;
                int area = height * left[i][j];
                ret = Math.max(ret, area);
            }
        }
        return ret;
    }
}

3、时间复杂度

时间复杂度 ： O(mn)

其中m和n是矩阵的行数和列数。

空间复杂度： O(mn)

其中m和n是矩阵的行数和列数。

三、总结

代码与84题代码基本类似。

思路就是：

• 枚举矩形的下边界，枚举下边界的每一列的高度
• 找到最高的柱子向左右寻找最大的矩形
• 得到矩形求出面积