Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
找到01矩形中最大的全1子矩阵。
我自己的思路：
我先用一个跟输入相同大小的矩阵numInCol 存储从当前位置开始向下有多少连续的1。
如
其numInCol 是
然后用一个变量tmpans来记录以某个位置开始，其右下矩形的最大全1矩阵的大小。
方法是如果当前位置是1，则用1 * numInCol[当前位置] 即只有这一列的大小
如果其后面紧接着的位置也是1，则用 2 * (这两列中连续1高度小的值) 即这两列的矩形大小
如果其后面紧接着的位置也是1，则用 3 * (这三列中连续1高度小的值) 即这三列的矩形大小
........................
依次类推
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std; class Solution {
public:
int maximalRectangle(vector<vector<char> > &matrix) {
if(matrix.empty())
return ; int row = matrix.size();
int col = matrix[].size();
int ans = ; vector<vector<int> > numInCol(row, vector<int>(col, ));
int tmpans = ; //对每一列
for(int j = ; j < col; j++)
{
numInCol[row - ][j] = (matrix[row - ][j] == '') ? : ;
for(int i = row - ; i >= ; i--)
{
if(matrix[i][j] == '')
{
numInCol[i][j] = numInCol[i + ][j] + ;
}
}
} //对整个矩阵
for(int i = row - ; i >= ; i--)
{
tmpans = numInCol[i][col - ];
ans = max(ans, tmpans);
for(int j = col - ; j >= ; j--)
{
int jj = j;
int len = ;
int minlen = numInCol[i][j];
while(jj < col && matrix[i][jj] == '')
{
minlen = min(minlen, numInCol[i][jj]);
tmpans = max(tmpans, len * minlen);
ans = max(ans, tmpans);
jj++;
len++; }
}
} return ans;
}
}; int main()
{
Solution s;
vector<vector<char> > matrix(, vector<char>(, ''));
matrix[][] = '';
matrix[][] = '';
matrix[][] = '';
matrix[][] = '';
matrix[][] = '';
matrix[][] = '';
matrix[][] = '';
matrix[][] = ''; int ans = s.maximalRectangle(matrix); return ;
}
网上的答案，整体的思路差不多，也是通过一列列的数据来判断，但是并没有像我一样，把所有的值都存下来，而是只存了一行的列信息，每到新的一行再更新，这样空间少了很多。其次，没有像我这样每次都循环后面的列是否为1，而是利用栈，如果高度是递增的就先不计算最大矩形而是把信息压栈，等到遇到高度减少的时候再依次计算这一段的最大矩形。
class Solution {
public:
int maximalRectangle(vector<vector<char>> &matrix) {
if (matrix.empty()) return ;
int rows = matrix.size();
int cols = matrix[].size();
int maxArea = ;
vector<int> heights(cols + , );
vector<int> stack;
for (int i = ; i < rows; i++) {
stack.clear();
for (int j = ; j < cols + ; j++) {
if (j < cols) {
if (matrix[i][j] == '') {
heights[j]++;
} else {
heights[j] = ;
}
}
if (stack.empty() || heights[j] >= heights[stack.back()]) {
stack.push_back(j);
continue;
}
while (!stack.empty() && heights[j] < heights[stack.back()]) {
int top = stack.back();
stack.pop_back();
int begin = stack.empty() ? : stack.back() + ;
int area = heights[top] * (j - begin);
if (area > maxArea) maxArea = area;
}
stack.push_back(j);
}
}
return maxArea;
}
};