由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Maximal Rectangle TLE是指代码正确,但不是最优吗?
相关主题
有用java过Maximal Rectangle的judge large的吗?google的一道题求解
Maximal Rectangle O(mn) 解法 非 histogram有人面试碰到过Distinct Subsequences?
Largest Rectangle in Histogram不同算法的复杂度Google interview question
求Leetcode OJ Maximal Rectangle的n^2解法请问一道题--给一个正方形矩阵,每个元素要么黑色要么白色,请找出最大的纯色子矩阵
再问Maximal Rectangle的N^2解法算法--一个MXN matrix (0's and 1's)内求最大 rectangle(1's)
Question about Leetcode: Maximum rectanglehistogram问题
我也来问问LC的Maximal Rectangleleetcode一道题
问一道G家面试题Modified Maximal Rectangle problem from Leetcode
相关话题的讨论汇总
话题: int话题: col话题: row话题: vector话题: maxarea
进入JobHunting版参与讨论
1 (共1页)
a***e
发帖数: 413
1
这样是不是 O(N^N)的复杂度?
class Solution {
public:
int maximalRectangle(vector > &matrix) {
int row=matrix.size();
if (row==0) return 0;
int col=matrix[0].size();
if (col==0) return 0;

//find all disjoint rectangles
vector> flag(row, vector(col,false));
int maxArea=INT_MIN;

for (int r=0; r for (int c=0; c {
int area=0;
if (matrix[r][c]=='1'&&flag[r][c]==false)
{
area+=helper(matrix,r,c,flag, row, col);
}
maxArea=max(maxArea,area);
}

return maxArea;
}

int helper(vector> &m, int r, int c, vector> f
, int row, int col)
{
if (r {
if (f[r][c]=false&&m[r][c]=='1')
f[r][c]=true;
if (r+1 {
f[r+1][c]=true;
return (2+helper(m,r+2,c,f,row,col));
}
if (c+1 {
f[r][c+1]=true;
return (2+helper(m,r,c+2,f,row,col));
}
return 1;
}
else
return 0;
}
};
1 (共1页)
进入JobHunting版参与讨论
相关主题
Modified Maximal Rectangle problem from Leetcode再问Maximal Rectangle的N^2解法
leetcode Maximal Rectangle的测试数据有问题?Question about Leetcode: Maximum rectangle
OJ里面的Maximal Rectangle我也来问问LC的Maximal Rectangle
求最大submatrix sum问一道G家面试题
有用java过Maximal Rectangle的judge large的吗?google的一道题求解
Maximal Rectangle O(mn) 解法 非 histogram有人面试碰到过Distinct Subsequences?
Largest Rectangle in Histogram不同算法的复杂度Google interview question
求Leetcode OJ Maximal Rectangle的n^2解法请问一道题--给一个正方形矩阵,每个元素要么黑色要么白色,请找出最大的纯色子矩阵
相关话题的讨论汇总
话题: int话题: col话题: row话题: vector话题: maxarea