Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
--------------------------------------------
方法1：O(m * n) 解法来自google，借用了上一题Largest Rectangle Area的代码
将每一行都看做x轴，在每一个列上的连续1的个数则为当前列的y值，计算出当前行的最大矩形面积
class Solution {
public:
// from the question Largest Rectangle Area
int largestRectangleArea(vector<int> &height) {
stack<int> st;
int largest = 0;
height.push_back(0);
for (int i = 0; i < height.size(); i++) {
if (st.empty() || height[i] >= height[st.top()]) {
st.push(i);
}else {
int topBar = st.top();
st.pop();
if (st.empty()) {
largest = max(largest,height[topBar] * i);
}else {
largest = max(largest,height[topBar] * (i - st.top() - 1));
}
i--;
}
}
return largest;
}
int maximalRectangle(vector<vector<char> > &matrix) {
if (matrix.size() == 0) return 0;
vector<int> heights(matrix[0].size(),0);
int largest = 0;
for (int row = 0; row < matrix.size(); row++) {
for (int col = 0; col < matrix[0].size(); col++) {
if (matrix[row][col] == '1') {
heights[col]++;
}else {
heights[col] = 0;
}
}
largest = max(largest, largestRectangleArea(heights));
}
return largest;
}
};
方法2：O(m * n * m)
dp[i][j]存的是以（i,j）为起点往右，在该行上连续的1的个数
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0) return 0;
int n = matrix[0].size();
vector<vector<int>> dp(m,vector<int>(n + 1,0));
for (int i = 0; i < m; i++) {
for (int j = n - 1; j >= 0; j--) {
if (matrix[i][j] == '1') {
dp[i][j] = dp[i][j + 1] + 1;
}
}
}
int largest = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int width = dp[i][j];
for (int k = i; k < m && width > 0; k++) {
width = min(dp[k][j],width);
largest = max(largest,width * (k - i + 1));
}
}
}
return largest;
}
};
方法3：COME_BACK
height[i]是在（i, j）上1的高度，如果matrix[i][j] = 0，则height[i] = 0
left[i]是底边包含(i, j)，高度为height[i]矩阵的最左边的index，right[i]类似
（找个例子，走一边就信服了）
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0) return 0;
int n = matrix[0].size();
vector<int> left(n,0);
vector<int> right(n,n - 1);
vector<int> height(n,0);
int largest = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
height[j]++;
}else {
height[j] = 0;
}
}
int furLeft = 0;
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
left[j] = max(furLeft,left[j]);
}else {
furLeft = j + 1;
left[j] = 0;
}
}
int furRight = n - 1;
for (int j = n - 1; j >= 0; j--) {
if (matrix[i][j] == '1') {
right[j] = min(furRight,right[j]);
}else {
furRight = j - 1;
right[j] = n - 1;
}
}
for (int j = 0; j < n; j++) {
largest = max(largest,height[j] * (right[j] - left[j] + 1));
}
}
return largest;
}
};
