这道题很难想，主要有两种解法，一种是把这道题目转化成之前那道（#084）直方图面积计算的题目，使用栈来做，但是还有更优雅的方法，使用DP。这两种方法的时间复杂度都是O(mn)，空间复杂度都是O(n)。
题目
Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 6.
解法一：直方图面积
行遍历，沿着这一行将矩阵切开，行上面的矩阵看做#84题目中的直方图，计算上面直方图面积的最大值。在遍历所有行之后，得到的面积最大值就是最大面积。
解法二：DP
行遍历，沿着一行进行扫描，我们对于矩阵中的每个位置需要维护三个量：H 高度， L 左边界， R 右边界，这三个量将被用来计算一个矩形面积
0 0 0 1 0 0 0
0 0 1 1 1 0 0
0 1 1 1 1 1 0
我们来考虑上面的矩阵
在遍历第一行时，
高度H：0001000
遍历第二行时，只需要考虑前一行已存储的状态和这一行的值就可以了，直接在H的基础上修改就可以了
高度H：0012100
对于左右边界，情况复杂一点，需要考虑前一行存储的状态和这一行已扫面过的状态
遍历第一行时，
左边界L：0003000
遍历第二行时，
左边界L：0023200
在下面的代码中，使用curleft存储的值表示当前块的最左边，在最终决定左边界时，要考虑到上一行如果已经有已存在的左边界时，就选取上一行左边界值作为当前左边界（如第二行L的232中的3）。
这样每一行遍历时，内部就可以表示不同起始边界的矩形块了。
右边界同理。
该动态规划的过程就是利用了上一行的信息。
DP代码
一个容易理解的版本，后面还有一个做了代码优化的版本
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int res = 0;
const int m = matrix.size();
if (m == 0){
return 0;
}
const int n = matrix[0].size();
if (n == 0){
return 0;
}
vector<int> left(n, 0), right(n, n), height(n, 0);
for (int i = 0; i < m; ++i){
int cur_left = 0, cur_right = n;
for (int j = 0; j < n; ++j){
height[j] = matrix[i][j] == '1' ? height[j] + 1 : 0; // ==1, 则height++,否则为0
}
for (int j = 0; j < n; ++j){
left[j] = matrix[i][j] == '1' ? max(left[j], cur_left) : 0; // ==1 左边界 为 最右,否则为0
cur_left = matrix[i][j] == '1' ? cur_left : j + 1; // ==1， 左边界不变，否则无效
}
for (int j = n - 1; j >= 0; --j){
right[j] = matrix[i][j] == '1' ? min(right[j], cur_right) : n;
cur_right = matrix[i][j] == '1' ? cur_right : j;
}
for (int j = 0; j < n; ++j){
res = max(res, (right[j] - left[j]) * height[j]); // 计算面积
}
}
return res;
}
};
做了一些代码优化，6ms，轻松超过90%
class Solution {
public:
int maximalRectangleCodeOP(vector<vector<char>>& matrix) {
int res = 0;
const int m = matrix.size();
if (m == 0){
return 0;
}
const int n = matrix[0].size();
if (n == 0){
return 0;
}
vector<int> left(n, 0), right(n, n), height(n, 0);
for (int i = 0; i < m; ++i){
int cur_left = 0, cur_right = n;
for (int j = n - 1; j >= 0; --j){
right[j] = matrix[i][j] == '1' ? min(right[j], cur_right) : n;
cur_right = matrix[i][j] == '1' ? cur_right : j;
}
for (int j = 0; j < n; ++j){
const bool flag = matrix[i][j] == '1';
height[j] = flag ? height[j] + 1 : 0;
left[j] = flag ? max(left[j], cur_left) : 0;
cur_left = flag ? cur_left : j + 1;
res = max(res, (right[j] - left[j]) * height[j]);
}
}
return res;
}
};