【动态规划】leetcode85 最大矩形（Java）

题目详情

题目解析

动态规划
设置动态规划数组 dp[][] 数组中的元素表示 grid[i][j] 为1 时其右侧连续1的数目，然后向上寻找能形成的矩形的面积。

width = dp[i][j];
for(int k = i; k >= 0; k --){
    if(dp[k][j] == 0)
        break;
    if(dp[k][j] >= width)
        curArea = width * (i - k + 1);
    else{
        curArea = dp[k][j] * (i - k + 1);
        width = dp[k][j];
    }                   
    maxArea = Math.max(curArea, maxArea);

整体代码

/**
 * 动态规划
 */

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length == 0)
            return 0;
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] dp = new int[row][col];
        if(matrix[0][0] == '1')
            dp[0][0] = 1;
        else
            dp[0][0] = 0;
        int maxArea = dp[0][0];
        int curArea = 0;
        // 初始化 第 0 行
        for(int j = 1; j < col; j ++){
            if(matrix[0][j] == '0')
                dp[0][j] = 0;
            else
                dp[0][j] = dp[0][j - 1] + 1;
            maxArea = Math.max(maxArea, dp[0][j]);
        }
        // 初始化 第 0 列
        for(int i = 1; i < row; i ++){
            if(matrix[i][0] == '0')
                dp[i][0] = 0;
            else{
                dp[i][0] = 1;
                for(int k = i; k >= 0; k --){
                    if(dp[k][0] == 0)
                        break;
                    curArea = i - k + 1;
                    maxArea = Math.max(maxArea, curArea);
                }
            }
        }
        int width = 0;

        for(int i = 1; i < row; i ++){
            for(int j = 1; j < col; j ++){
                if(matrix[i][j] == '0')
                    dp[i][j] = 0;
                else{
                    dp[i][j] = dp[i][j - 1] + 1;
                    width = dp[i][j];
                    for(int k = i; k >= 0; k --){
                        if(dp[k][j] == 0)
                            break;
                        if(dp[k][j] >= width)
                            curArea = width * (i - k + 1);
                        else {
                            curArea = dp[k][j] * (i - k + 1);
                            width = dp[k][j];
                        }
                        maxArea = Math.max(curArea, maxArea);
                        System.out.println(maxArea);
                    }
                }
            }
        }
        return maxArea;
    }
}