题目描述： 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例: 输入: [ [“1”,“0”,“1”,“0”,“0”], [“1”,“0”,“1”,“1”,“1”], [“1”,“1”,“1”,“1”,“1”], [“1”,“0”,“0”,“1”,“0”] ] 输出: 6 方法1：动态规划 主要思路： （1）使用heights[ i ][ j ]表示当前位置中，字符 ‘1’ 可以形成的高度，若matrix[ i-1][j-1] 处的字符为 ‘0’ ，则高度为 0 直接跳过，若为字符 ‘1’，则需要增加高度，既 heights[i][j]=heights[i-1][j]+1； （2）在增加了高度后，可以更新在增加了该字符后，能不能在之前的面积的后面的一列上，增加新的面积，则使用 dp[i ][ j ] [ k ] 表示 i，j处各个高度下可能形成的面积，既 dp [ i][j][k] = dp[i][j-1][k]+k； （3）使用中间变量保存可能的最大面积，既 res=max(res,dp[i][j][k]);
class Solution { public: int maximalRectangle(vector<vector<char>>& matrix) { if(matrix.empty()||matrix[0].empty()) return 0; int res=0; int rows=matrix.size(); int cols=matrix[0].size(); vector<vector<int>> heights(rows+1,vector<int>(cols+1,0)); vector<vector<vector<int>>>dp(rows+1,vector<vector<int>>(cols+1,vector<int>(rows+1,0))); for(int i=1;i<=rows;++i){ for(int j=1;j<=cols;++j){ if(matrix[i-1][j-1]=='0') continue; heights[i][j]=heights[i-1][j]+1; for(int k=1;k<=heights[i][j];++k){ dp[i][j][k]=dp[i][j-1][k]+k; res=max(res,dp[i][j][k]); } } } return res; } };