Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
最土的做法无疑就是遍历矩阵中的所有矩形,时间复杂度为O(n^2 * m ^2)不用试估计也会超时了,看了讨论组里面有位大神提供了这样的思路:
This question is similar as [Largest Rectangle in Histogram]:
You can maintain a row length of Integer array H recorded its height of '1's, and scan and update row by row to find out the largest rectangle of each row.
You can maintain a row length of Integer array H recorded its height of '1's, and scan and update row by row to find out the largest rectangle of each row.
什么意思呢?给大家用图例展示一下:想看详细步骤的可以戳这里:
虽然上图画错了,但是还是表达出了大神的意思:
对原矩阵matrix的每一行生成并维护一个int[]数组。
这个数组表示以该行为底线,与上面所有行组成的高度数组,比如第三行是0 1 1 1,但是matrix[1][3] 也是1,因此最有一个元素的高度应该是2(图中只花了1个高度)
思考一下:第2行第三个元素是0,但是它上面是1,为什么高度和是0而不是1呢?(想不通面壁去)
因此我们可以由matrix的每一行生成一个int[]高度数组,是不是回到了[Largest Rectangle in Histogram]?
因此我们要做的就是对每一行生成一个int[]数组。再对每个int[]数组调用Largest Rectangle in Histogram中的方法即可。
public int maximalRectangle(char[][] matrix) { if(matrix == null || matrix.length == 0) return 0; int rowCount = matrix.length; int columnCount = matrix[0].length; int[][] rectangle = new int[rowCount][columnCount]; for(int i = 0; i < rowCount; i++){ for(int j = 0; j < columnCount;j++){ if(i == 0){ rectangle[i][j] = matrix[i][j] == '1' ? 1 : 0; }else{ rectangle[i][j] = matrix[i][j] == '1' ? 1 + rectangle[i - 1][j] : 0; } } } int maxArea = 0; for(int i = 0; i < rowCount; i++){ int tem = getLargestRectangle(rectangle[i]); maxArea = tem > maxArea ? tem : maxArea; } return maxArea; }
下面是Largest Rectangle in Histogram中的源代码,一模一样,而且两道题在leetcode中的位置也是挨着的,算是提示吗?
private int getLargestRectangle(int[] height){ int[] copy = new int[height.length + 1]; copy = Arrays.copyOf(height, height.length + 1); Stack<Integer> stack = new Stack<Integer>(); int maxArea = 0; int i = 0; while(i < copy.length){ if(stack.isEmpty() || copy[stack.peek()] < copy[i]){ stack.push(i++); }else{ int num = stack.pop(); maxArea = Math.max(maxArea,copy[num] * (stack.isEmpty() ? i : i - stack.peek() - 1)); } } return maxArea; }
相关推荐
LeetCode题目Largest Rectangle in Histogram 解答
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
1. Introduction 2. Array i. Remove Element ... Maximal Rectangle x. Palindrome Number xi. Search a 2D Matrix xii. Search for a Range xiii. Search Insert Position xiv. Find Peak Element
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
vs code LeetCode 插件
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
leetcode中文版
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 Java,部分有解释 ...norvig神牛Python代码...Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
Rectangle Monotonic stack for 2d array 239. Sliding Window Maximum 255. Verify Preorder Sequence in Binary Search Tree 907. Sum of Subarray Minimums 二叉搜索树 99. Recover Binary Search Tree 109. ...
Rectangle 栈 局部递增 或者 动态规划 Binary Tree Inorder Traversal 栈 递归 Single Number 异或 Copy List with Random Pointer 单链表 map Max Points on a Line 斜率 map, int> Fraction to Recurring Decimal ...
100个leetCode详细解答
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
LeetCode 刷题汇总1
LeetCode 选讲1
leetcode 316 LeetCode Summary Exclusive Time of Functions: 栈 Friend Circles:DFS Print Binary Tree:二叉树 Maximal Square:DP Maximal Rectangle:单调栈(Histogram变形) Largest Rectangle in Histogram:...
maximal rectangle :dp问题,较难 largestRectangleArea 求直方图的最大面积,左右两次扫面+剪枝优化 Valid Parentheses 用栈判断括号匹配 Regular Expression Matching 递归匹配 wildcard matching 动态规划 ...
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...