原题链接:http://oj.leetcode.com/problems/maximal-rectangle/这是一道非常综合的题目,要求在0-1矩阵中找出面积最大的全1矩阵。刚看到这道题会比较无从下手,brute force就是对于每个矩阵都看一下,总共有m(m+1)/2*n(n+1)/2个子矩阵(原理跟字符串子串类似,字符串的子串数有n(n+1)/2,只是这里是二维情形,所以是两个相乘),复杂度相当高,肯定不是面试官想要的答案,就不继续想下去了。这道题的解法灵感来自于Largest
Rectangle in Histogram这道题,假设我们把矩阵沿着某一行切下来,然后把切的行作为底面,将自底面往上的矩阵看成一个直方图(histogram)。直方图的中每个项的高度就是从底面行开始往上1的数量。根据Largest
Rectangle in Histogram我们就可以求出当前行作为矩阵下边缘的一个最大矩阵。接下来如果对每一行都做一次Largest
Rectangle in Histogram,从其中选出最大的矩阵,那么它就是整个矩阵中面积最大的子矩阵。算法的基本思路已经出来了,剩下的就是一些节省时间空间的问题了。我们如何计算某一行为底面时直方图的高度呢? 如果重新计算,那么每次需要的计算数量就是当前行数乘以列数。然而在这里我们会发现一些动态规划的踪迹,如果我们知道上一行直方图的高度,我们只需要看新加进来的行(底面)上对应的列元素是不是0,如果是,则高度是0,否则则是上一行直方图的高度加1。利用历史信息,我们就可以在线行时间内完成对高度的更新。我们知道,Largest
Rectangle in Histogram的算法复杂度是O(n)。所以完成对一行为底边的矩阵求解复杂度是O(n+n)=O(n)。接下来对每一行都做一次,那么算法总时间复杂度是O(m*n)。空间上,我们只需要保存上一行直方图的高度O(n),加上Largest
Rectangle in Histogram中所使用的空间O(n),所以总空间复杂度还是O(n)。代码如下:public int maximalRectangle(char[][] matrix) {
if(matrix==null || matrix.length==0 || matrix[0].length==0)
{
return 0;
}
int maxArea = 0;
int[] height = new int[matrix[0].length];
for(int i=0;i<matrix.length;i++)
{
for(int j=0;j<matrix[0].length;j++)
{
height[j] = matrix[i][j]=='0'?0:height[j]+1;
}
maxArea = Math.max(largestRectangleArea(height),maxArea);
}
return maxArea;
}
public int largestRectangleArea(int[] height) {
if(height==null || height.length==0)
{
return 0;
}
int maxArea = 0;
LinkedList<Integer> stack = new LinkedList<Integer>();
for(int i=0;i<height.length;i++)
{
while(!stack.isEmpty() && height[i]<=height[stack.peek()])
{
int index = stack.pop();
int curArea = stack.isEmpty()?i*height[index]:(i-stack.peek()-1)*height[index];
maxArea = Math.max(maxArea,curArea);
}
stack.push(i);
}
while(!stack.isEmpty())
{
int index = stack.pop();
int curArea = stack.isEmpty()?height.length*height[index]:(height.length-stack.peek()-1)*height[index];
maxArea = Math.max(maxArea,curArea);
}
return maxArea;
}
这道题最后的复杂度是非常令人满意的,居然在O(m*n)时间内就可以完成对最大矩阵的搜索,可以看出这已经是下界(因为每个元素总要访问一下才知道是不是1)了。难度还是比较大的,相信要在面试当场想到这种方法是很不容易的。个人很喜欢这道题,既用到了别的题目,又有动态规划的思想,复杂度还非常漂亮,又一次体现了算法的魅力哈。
分享到:
相关推荐
关于论文MaPle A Fast Algorithm for Maximal Pattern-based Clustering∗的翻译
图论资料,仅供学习使用,方便自己平时学习资料查阅,日常讲义积累,请勿用作商业用途,On Sparse Maximal 2-Planar Graphs
Rectangle 栈 局部递增 或者 动态规划 Binary Tree Inorder Traversal 栈 递归 Single Number 异或 Copy List with Random Pointer 单链表 map Max Points on a Line 斜率 map, int> Fraction to Recurring Decimal ...
Auslander’s 1-Gorenstein代数上平凡的极大1-正交子范畴,黄兆泳,张孝金,设Λ是一个整体维数为2的Auslander’s 1-Gorenstein代数。如果mod Λ中有一个平凡的极大1-正交子范畴,则对mod Λ中的任意不可分解模M,M...
maximal rectangle :dp问题,较难 largestRectangleArea 求直方图的最大面积,左右两次扫面+剪枝优化 Valid Parentheses 用栈判断括号匹配 Regular Expression Matching 递归匹配 wildcard matching 动态规划 ...
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 Java,部分有解释 ...norvig神牛Python代码...Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
leetcode 316 LeetCode Summary Exclusive Time of Functions: 栈 Friend Circles:DFS Print Binary Tree:二叉树 Maximal Square:DP Maximal Rectangle:单调栈(Histogram变形) Largest Rectangle in Histogram:...
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. ...
A new maximal-margin spherical-structured multi-class support vector machine Pei-Yi Hao · Jung-Hsien Chiang · Yen-Hsiu Lin Published online: 18 October 2007 © Springer Science+Business Media, LLC ...
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
MATLAB code for Massive MIMO
First, when the inter-user distance d is small, the SNR for D2D communication is high, and hence there are sufficient number of bits for high quality CSI exchange.
力扣最大面积最大矩形 给定一个由 0 和 1 填充的二维二进制矩阵,找到仅包含 1 的最大矩形并返回其面积。 Example: Input: [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ...=
部分排序leetcode 竞争性编程 我在 Codeforces、Codechef、LeetCode、Hackerrank 和 AtCoder 上的代码库 编解码器 彻底解决: ...Maximal Continuous Rest (A) Equalize Prices Again (B) Odd Sum Segments
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
B型和D型极大抛物型Kazhdan-Lusztig R-多项式,范久瑜,,在本文中,我们给出了某些$B$型和$D$型极大抛物型Kazhdan-Lusztig $R$-多项式的显式表达式。记$B_n$为$B$型Coxeter群,生成元集记为$S_n^B={s_0,s_1,ldot
MOMS(最大阶最小支持)函数为给定的近似阶 L 提供最少的支持数。支持数的严格要求对于实时信号处理至关重要,这就是为什么 sinc(给出理想重建)在实践中不使用。 基于 B 样条的插值内核通常用于样条插值。...
leetcode 和 oj 编程问题 在线裁判网站问题解决方案 如果您遇到这个问题并对如何更好地完成某些解决方案有建议或意见,欢迎您。 palin.ml : ...MaximalRectangle : oj.leetcode 问题的java解决方案
数据挖掘相关内容Redundancy-Aware Maximal Cliques,关于最大派系
In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. As an example, the maximal sub-rectangle of the array: 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 –2 is ...