算法精粹(algorithm-essentials)

感谢soulmachine@github提供内容
## Maximal Rectangle


### 描述

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.


### 分析




### 代码

{% if book.java %}
{% codesnippet "./code/maximal-rectangle."+book.suffix, language=book.suffix %}{% endcodesnippet %}
{% endif %}

{% if book.cpp %}
```cpp
// Maximal Rectangle
// 时间复杂度O(n^2),空间复杂度O(n)
class Solution {
public:
int maximalRectangle(vector > &matrix) {
if (matrix.empty()) return 0;

const int m = matrix.size();
const int n = matrix[0].size();
vector H(n, 0);
vector L(n, 0);
vector R(n, n);

int ret = 0;
for (int i = 0; i < m; ++i) {
int left = 0, right = n;
// calculate L(i, j) from left to right
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;
}
}
// calculate R(i, j) from right to left
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;
}
};
```
{% endif %}