题解 | #最大矩形#

把每一列的1累加起来，遇到0重新开始累加，记录到一个新的矩阵中，对这个矩阵进行遍历。

class Solution {
public:
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param matrix int整型vector<vector<>> 
 * @return int整型
 */
int maximalRectangle(vector<vector<int> >& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    
    vector<vector<int> > colunmMatrix(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 || matrix[i][j] == 0) {
                colunmMatrix[i].push_back(matrix[i][j]);
            } else {
                colunmMatrix[i].push_back(matrix[i][j] + colunmMatrix[i - 1][j]);
            }
        }
    }
    int max = 0;
    for (int i = n - 1; i >= 0; i--) {
        vector<int>& oneRow = colunmMatrix[i];
        for (int j = 0; j < m; j++) {
            int rowMin = 0;
            //对于每一个非0的点，往后进行遍历看看能组成多大的矩形（注意，矩阵的高为所有点中的最小值，遇到0就停止）
            for (int k = j; k < m; k++ ) {
                if (oneRow[k] == 0) {
                    break;
                }
                if (rowMin == 0 || oneRow[k] < rowMin) {
                    rowMin = oneRow[k];
                }
                int count = rowMin * (k - j + 1);
                if (count > max) {
                    max = count;
                }
            }
        }
    }
    return max;
}
};