s*********s
发帖数: 140 | 1 求能过Large Judge的N^2 Maximal Rectangle的code
http://tianrunhe.wordpress.com/2012/08/03/maximal-rectangle-wit 这个是转化为largest rectangle under histogram的N^2解法，但是过不了large judge，说是time limit exceed。自己用另外一种方法写了个N^3次方的倒是large judge能过。。。想知道能过large judge的N^2解法该怎么写。
大牛们贴一下N^2的code吧。。。 | h****n
发帖数: 1093 | 2 large rectangle in histogram的变形，那个会N解法的话，自然这个就是N square解
法 | s*********s
发帖数: 140 | 3 恩，那个blog的解法是基于histogram那道题的。但是large judge会报time limit
exceeded.我自己写了一遍也过不了large judge。能帮忙看看是哪里的时间复杂度太高
呢？
public class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix == null || matrix.length == 0)
return 0;
int max = 0;
for(int i = 0; i < matrix[0].length; i++){
int[] height = getHeight(matrix, i);
max = Math.max(max, largestRectangleArea(height));
}
return max;
}
int[] getHeight(char[][] matrix, int offset){
int w = matrix.length;
int h = matrix[0].length;
int[] height = new int[w];
for(int i = 0; i < w; i++){
int count = 0;
for(int j = offset; j < h; j++) {
if(matrix[i][j] == '1'){
count++;
} else {
height[i] = count;
break;
}
if(count > 0) height[i] = count;
}
}
return height;
}
int largestRectangleArea(int[] height) {
if(height == null || height.length == 0) return 0;
Stack st = new Stack();
int max = 0;
int r = 0;
int n = height.length;
while(r < n){
if(st.isEmpty()){
st.push(r);
r++;
continue;
}
int l = st.peek();// the potential left border.
if(height[l] > height[r]){
while(!st.isEmpty() && height[l] > height[r]){
int curr = st.pop();
l = st.isEmpty()?-1:st.peek();
max = Math.max(max, height[curr] * (r-l-1));
}
} else if(height[l] == height[r]) {
st.pop();
}
st.push(r);
r++;
}
while(!st.isEmpty()){
int curr = st.pop();
int l = st.isEmpty()?-1:st.peek();
max = Math.max(max, height[curr] * (n-l-1));
}
return max;
}
}
【在 h****n 的大作中提到】
: large rectangle in histogram的变形，那个会N解法的话，自然这个就是N square解
: 法
| c**s
发帖数: 159 | 4 int maximalRectangle(vector > &matrix) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int m = matrix.size();
if (m == 0) {
return 0;
}
int n = matrix[0].size();
vector height;
height.resize(n,0);
stack > st;
int i, j ,answer = 0;
for (i = 0; i < m; ++i) {
for (j = 0; j < n; ++j) {
if (matrix[i][j] == '1') {
++height[j];
}
else {
height[j] = 0;
}
while (!st.empty() && height[st.top().first] > height[j]) {
answer = max(answer, height[st.top().first] * (j - st.top().
second));
st.pop();
}
st.push(make_pair(j,st.empty()?(0):(st.top().first + 1)));
}
while (!st.empty()) {
answer = max(answer, height[st.top().first] * (n - st.top().
second));
st.pop();
}
}
return answer;
} | f**********n
发帖数: 258 | 5 用stl stack模拟单调队列,速度要比下面这种单调队列写法慢很多,这种写法和并查集
的快速压缩本质是一样的。 有兴趣可以把POJ 1964 2082 2559 2796 3250 3494全部过
掉.
http://blog.csdn.net/niuqingpeng/article/details/8192769
void RectangularArea(int n)
{
vector L(n+2,0);
vector R(n+2,0);
high[0] = high[n + 1] = -1; //初始化边界，防止越界判错
for (int i = 1; i <= n; i ++) //把L[], R[]赋值为本身
{ L[i] =i; R[i] = i;}
for (int i = 1; i <= n; i ++)
while(high[L[i] - 1] >= high[i]) //确定l[i]的最高左位置
L[i] = L[L[i] - 1];
for (int i = n; i >= 1; i --)
while (high[R[i] + 1] >= high[i]) //确定r[i]的最高右位置
R[i] = R[R[i] + 1];
int ans = 0;
for (int i = 1; i <= n; i ++)
ans = max(high[i] * (Sigma[R[i]] - Sigma[L[i]-1] ), ans); //得到最大
的连续矩形面积（单位长度是1）
printf("%d\n", ans);
} |
|
