图形最大面积

矩形最大面积

85. 最大矩形 hard

LCR 040. 最大矩形

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

遍历每一层, 每次迭代按柱子组成的最大矩形处理
求左右不矮于当前柱子的索引, 一般用单调栈处理

解法 1 单调栈

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int r = matrix.length, c = matrix[0].length;
        int res = 0;
        int[] height = new int[c];
        for (int i = 0; i < r; i++) {
            // dp, 上一层的转移
            for (int j = 0; j < c; j++) {
                if (matrix[i][j] == '1') height[j]++;
                else height[j] = 0;
            }
            int[] left = new int[c];
            int[] right = new int[c];
            Arrays.fill(right, c - 1);
            Deque<Integer> stack = new ArrayDeque<>();
            for (int j = 0; j < c; j++) {
                // 严格矮的
                while (!stack.isEmpty() && height[stack.peek()] > height[j]) {
                    right[stack.pop()] = j - 1;
                }
                if (!stack.isEmpty()) left[j] = stack.peek() + 1;
                stack.push(j);
            }
            for (int j = 0; j < c; j++) {
                res = Math.max(res, height[j] * (right[j] - left[j] + 1));
            }
        }
        return res;
    }
}

解法 2 dp

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int r = matrix.length, c = matrix[0].length;
        int res = 0;
        int[] height = new int[c];
        int[] left = new int[c];
        int[] right = new int[c];
        Arrays.fill(right, c - 1);
        for (int i = 0; i < r; i++) {
            // dp, 上一层的转移
            for (int j = 0; j < c; j++) {
                if (matrix[i][j] == '1') height[j]++;
                else height[j] = 0;
            }
            // 有效边界
            int boundary = 0;
            for (int j = 0; j < c; j++) {
                // 沿用上层的左边界或者更新为本层的左边界
                if (matrix[i][j] == '1') left[j] = Math.max(left[j], boundary);
                else {
                    // 左边界重置
                    left[j] = 0;
                    // 更新有效边界
                    boundary = j + 1;
                }
            }
            boundary = c - 1;
            for (int j = c - 1; j >= 0; j--) {
                if (matrix[i][j] == '1') right[j] = Math.min(right[j], boundary);
                else {
                    right[j] = c - 1;
                    boundary = j - 1;
                }
            }
            for (int j = 0; j < c; j++) {
                res = Math.max(res, height[j] * (right[j] - left[j] + 1));
            }
        }
        return res;
    }
}

221. 最大正方形 mid

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

最大正方形跟最大矩形不同, 可以 dp
DP: 右下角坐标为[i][j]的小正方形 的边长
$dp[i][j]=1+min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])$

class Solution {
    public int maximalSquare(char[][] matrix) {
        int maxEdge = 0;
        int r = matrix.length, c = matrix[0].length;
        int[][] dp = new int[r][c];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0)
                        dp[i][j] = 1;
                    else
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;

                    maxEdge = Math.max(maxEdge, dp[i][j]);
                }
            }
        }
        return maxEdge * maxEdge;
    }
}