由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Question about Leetcode: Maximum rectangle
相关主题
Maximal Rectangle O(mn) 解法 非 histogramleetcode一道题
求Leetcode OJ Maximal Rectangle的n^2解法Largest Rectangle in Histogram不同算法的复杂度
Maximal Rectangle TLE是指代码正确,但不是最优吗?Modified Maximal Rectangle problem from Leetcode
刚看了leetcode 上的maximum rectangular sub matrix那题leetcode container with most water
再问Maximal Rectangle的N^2解法leetcode: largest rectangle in histogram求帮助
有用java过Maximal Rectangle的judge large的吗?如何做LeetCode
我也来问问LC的Maximal RectangleMaximal Rectangle如果不要求是Rectangle就要简单得多
maximum rectangle in histogram 到底是个什么问题?google 面试题
相关话题的讨论汇总
话题: int话题: area话题: size话题: matrix话题: histogram
进入JobHunting版参与讨论
1 (共1页)
d*******u
发帖数: 186
1
Hello,
The following code can pass the Leetcode test, if it ran separately.
But it can not pass the Leetcode online. Any problem? thanks.
class Solution {
public:
int largestAreaunderHistogramv(vector histogram, int size)
{
stack histindexlessthan;
int *area = new int[size];

int left = -1;
//get Li
for(int i=0; i {
while(!histindexlessthan.empty())
{
if(histogram[i] <= histogram[histindexlessthan.top()])
histindexlessthan.pop();
else
break;
}
if(histindexlessthan.empty())
left = -1;
else
left = histindexlessthan.top();
histindexlessthan.push(i);
area[i] = i-left-1;
}
int right = size;
while(!histindexlessthan.empty())
histindexlessthan.pop();
//get Ri
for(int i=size-1; i>=0; i--)
{
while(!histindexlessthan.empty())
{
if(histogram[i] <= histogram[histindexlessthan.top()])
histindexlessthan.pop();
else
break;
}
if(histindexlessthan.empty())
right = size;
else
right = histindexlessthan.top();
histindexlessthan.push(i);
area[i] = area[i]+right-i-1;
}
int max=0;
for(int i=0; i {
area[i] = (area[i]+1) *histogram[i];//1: itself
if(area[i]>max)
max=area[i];
};
delete area;
return max;
}
int maximalRectangle(vector > &matrix) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
for(int i=1; i itself.
{
for(int j=0; j {
if( matrix[i][j] == 1)
matrix[i][j] =matrix[i-1][j] +1;
};
};
int *area = new int[matrix.size()];
int max=0;
vector arr;
for(int i=0; i {
arr.clear();
for(int j=0; j arr.push_back(matrix[i][j]);
area[i]=largestAreaunderHistogramv(arr, matrix[i].size());

if(arr[i]>max)
max=area[i];
}
delete area;
return max;

}
};
1 (共1页)
进入JobHunting版参与讨论
相关主题
google 面试题再问Maximal Rectangle的N^2解法
请问下leetcode的two sum题目有用java过Maximal Rectangle的judge large的吗?
新手请教:C++ decrement loop (转载)我也来问问LC的Maximal Rectangle
LeetCode: Spiral PrintMatrixmaximum rectangle in histogram 到底是个什么问题?
Maximal Rectangle O(mn) 解法 非 histogramleetcode一道题
求Leetcode OJ Maximal Rectangle的n^2解法Largest Rectangle in Histogram不同算法的复杂度
Maximal Rectangle TLE是指代码正确,但不是最优吗?Modified Maximal Rectangle problem from Leetcode
刚看了leetcode 上的maximum rectangular sub matrix那题leetcode container with most water
相关话题的讨论汇总
话题: int话题: area话题: size话题: matrix话题: histogram