问题描述:
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
原问题链接:https://leetcode.com/problems/maximal-rectangle/
问题分析
这个问题的解决思路其实依赖于前面一篇文章里求柱状图最大覆盖面积的思路。在前面的问题里,是针对一组数字求它所涵盖的面积。而这里因为提供的元素是一个矩阵,我们可以将它最初的一行当做一个柱状图,这样就可以得到一个最初始的最大涵盖面积。
当然,这只是针对最初始的情况。而这里因为是要求整个矩阵中标记为1的最大涵盖矩阵。我们再需要结合后面的行来考虑。以如下的矩阵为例:
1 1 0 1 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1
我们得到它们第一行的height数组是1 1 0 1 0 1,那么按照第一步我们计算出来的最大涵盖面积是2。在结合第二行的值时,我们更新第一行的数据。如果第二行里的元素是0,那么就将对应索引里的元素值更新为0,否则就是在原有索引的数值基础上加1。这样结合第二行我们得到的height数组是0 2 0 0 1 2,在用前面的办法来计算它的柱状图最大涵盖矩阵面积,得到它的最大面积是2。
我们依次按照上面的办法比较,最终可以得到如下的代码:
public class Solution { public int maximalRectangle(char[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0; int[] height = new int[matrix[0].length]; for (int i = 0; i < matrix[0].length; i++) { if (matrix[0][i] == '1') height[i] = 1; } int result = largestInLine(height); for (int i = 1; i < matrix.length; i++) { resetHeight(matrix, height, i); result = Math.max(result, largestInLine(height)); } return result; } private void resetHeight(char[][] matrix, int[] height, int idx) { for (int i = 0; i < matrix[0].length; i++){ if (matrix[idx][i] == '1') height[i] += 1; else height[i] = 0; } } public int largestInLine(int[] height) { if (height == null || height.length < 1) return 0; int[] stack = new int[height.length + 1]; int len = 0, max = 0; for (int i = 0; i <= height.length; i++) { int h = (i == height.length) ? 0 : height[i]; while (len != 0 && (i == height.length || height[stack[len - 1]] > h)) { if (len == 1) max = Math.max(height[stack[--len]] * i, max); else max = Math.max(height[stack[--len]] * (i - stack[len - 1] - 1), max); } stack[len++] = i; } return max; } }
参考材料
https://leetcode.com/discuss/52670/solution-based-maximum-rectangle-histogram-with-explanation
https://leetcode.com/discuss/104498/java-5ms-100%25-solution-by-modifying-bu-will-9s-solution
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
Leetcode:Leetcode提交
LeetCode 101:和你一起你轻松刷题(C++)
LeetCode题目Largest Rectangle in Histogram 解答
leetcode:leetcode刷题
Leetcode:LeetCode解题代码
LeetCode:LeetCode的代码
加油站问题leetcode LeetCode LeetCode-JS分类列表: :smiling_face_with_smiling_eyes: :flushed_face: :winking_face: :face_with_tongue: :face_with_open_mouth: :beaming_face_with_smiling_...
LeetCode:LeetCode的注释
leetcode:LeetCode问题