题解 | #最大矩形#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型vector<vector<>> 
     * @return int整型
     */
    int maximalRectangle(vector<vector<int> >& matrix) {
        // write code here
        
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(matrix[i][j] == 1){
                    dp[i][j] = j==0? 1: dp[i][j-1]+1;
                }
            }
        }
        
        int res = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(dp[i][j] > 0){
                    int width = dp[i][j];
                    int area = dp[i][j];
                    for(int k=i-1; k>=0; k--){
                        width = min(width, dp[k][j]);
                        area = max(area, width * (i-k+1));
                    }
                    res = max(res, area);
                }
            }
        }
        return res;
    }
};