b*********h
发帖数: 103 | 1 看讨论里 O(mn) 的解法都转化成了 histogram 下的最大矩形面积
其实如果读过《浅谈用极大化思想解决最大子矩形问题》这篇文章 里面介绍了一种悬
线法的 DP 时间复杂度是 O(mn) 的 原文图文讲解很好 实现起来也比 histogram 那个
容易一些
class Solution {
public:
int maximalRectangle(vector > &matrix) {
if (matrix.empty()) {
return 0;
}
int n = matrix[0].size();
vector H(n);
vector L(n);
vector R(n, n);
int ret = 0;
for (int i = 0; i < matrix.size(); ++i) {
int left = 0, right = n;
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == '1') {
++H[j];
L[j] = max(L[j], left);
}
else {
left = j+1;
H[j] = 0; L[j] = 0; R[j] = n;
}
}
for (int j = n-1; j >= 0; --j) {
if (matrix[i][j] == '1') {
R[j] = min(R[j], right);
ret = max(ret, H[j]*(R[j]-L[j]));
}
else {
right = j;
}
}
}
return ret;
}
}; |
j*****s
发帖数: 189 | 2 挺好，学些了
【在 b*********h 的大作中提到】
: 看讨论里 O(mn) 的解法都转化成了 histogram 下的最大矩形面积
: 其实如果读过《浅谈用极大化思想解决最大子矩形问题》这篇文章 里面介绍了一种悬
: 线法的 DP 时间复杂度是 O(mn) 的 原文图文讲解很好 实现起来也比 histogram 那个
: 容易一些
: class Solution {
: public:
: int maximalRectangle(vector > &matrix) {
: if (matrix.empty()) {
: return 0;
: }
|
f*******t
发帖数: 7549 | |
p*****2
发帖数: 21240 | |
a********3
发帖数: 228 | 5 怎么觉得最后一个else里面应该是
right = j + 1
啊 |
b*********h
发帖数: 103 | 6 是想说 j-1 吗？这里 left 和 right 类似于 begin 和 end，end 是指向最后一个元
素的下一个，这样在算长度的时候可以直接 right-left，而不是 right-left+1
stl 用的多会喜欢这样吧
【在 a********3 的大作中提到】
: 怎么觉得最后一个else里面应该是
: right = j + 1
: 啊
|
b*****n
发帖数: 482 | 7 很不错，谢谢分享，收藏一下。google了一下，貌似是一个中学生写的，很厉害啊，呵
呵。
【在 b*********h 的大作中提到】
: 看讨论里 O(mn) 的解法都转化成了 histogram 下的最大矩形面积
: 其实如果读过《浅谈用极大化思想解决最大子矩形问题》这篇文章 里面介绍了一种悬
: 线法的 DP 时间复杂度是 O(mn) 的 原文图文讲解很好 实现起来也比 histogram 那个
: 容易一些
: class Solution {
: public:
: int maximalRectangle(vector > &matrix) {
: if (matrix.empty()) {
: return 0;
: }
|
