leetcode 85. 最大矩形 困难

给定一个仅包含0和1、大小为rows x cols的二维二进制矩阵，找出只包含1的最大矩形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]输出：6解释：最大矩形如上图所示。

示例 2：

输入：matrix = [["0"]]输出：0

示例 3：

输入：matrix = [["1"]]输出：1

提示：

• rows == matrix.length
• cols == matrix[0].length
• 1 <= rows, cols <= 200
• matrix[i][j]为'0'或'1'

分析：先用一个 area 数组，记录坐标 (i,j) 处的矩形高度。当 matrix[i][j] 为 1时，判断是否为矩阵的第 1 行，如果是，则 area[i][j] 为 1；如果不是第一行，则 area[i][j]=1+area[i-1][j]，相当于在第 i-1 行第 j 列的位置下面垫了一层。统计完 area 数组后，用一个三重循环，计算从第 i 行第 j 列开始，向右可以获得的最大矩形面积，最后返回计算过程中最大的面积即可。

int maximalRectangle(char** matrix, int matrixSize, int* matrixColSize) { int n=matrixSize,m=matrixColSize[0],ans=0; int area[n+5][m+5]; for(int i=0;i<n;++i) { for(int j=0;j<m;++j) { area[i][j]=0; if(matrix[i][j]=='1') { if(!i)area[i][j]=1; else area[i][j]=1+area[i-1][j]; ans=fmax(ans,area[i][j]); } } } for(int i=0;i<n;++i) { for(int j=0;j<m;++j) { if(area[i][j]) { int sum=area[i][j],h=area[i][j]; for(int k=j+1;k<m;++k) { if(!area[i][k])break; else h=fmin(h,area[i][k]),sum=h*(k-j+1); ans=fmax(ans,sum); } } } } return ans; }