Java中(0,1)矩阵的最大全零子矩形计数方法咨询

Hey there! Let's break down how to solve this problem—you've already got a solid start with your areAllZeros function, so we just need to add logic to identify those maximal zero rectangles (the ones that can't be wrapped inside any larger all-zero rectangle).

先明确什么是「极大子矩形」 #

As you defined it: a zero subrectangle is maximal if there's no larger all-zero rectangle that completely contains it. Put another way, it can't be expanded in any direction (up, down, left, right) while still staying entirely within zeros.

For your example matrix:

Row 0: 0 0 1 0 0 0 0 0
Row 1: 0 0 0 0 0 0 0 0

The 3 maximal rectangles are exactly the ones you listed because none of them can be expanded into a bigger all-zero rectangle without hitting a 1 or the matrix edge.

核心思路：判断矩形是否无法扩展 #

To check if an all-zero rectangle is maximal, we just need to verify that it can't be expanded in any direction:

• Up: If there's a row above the rectangle, that row must have at least one 1 in the columns covered by the rectangle.
• Down: If there's a row below, that row must have at least one 1 in the rectangle's columns.
• Left: If there's a column to the left, that column must have at least one 1 in the rectangle's rows.
• Right: If there's a column to the right, that column must have at least one 1 in the rectangle's rows.

If all these conditions are met, the rectangle can't be expanded into a larger all-zero rectangle, so it's maximal.

代码实现 #

First, let's add a helper function to check if a rectangle is maximal:

static boolean isMaximal(int[][] matrix, int top, int left, int height, int width) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int bottom = top + height;
    int right = left + width;

    // Check if we can expand upward
    if (top > 0) {
        boolean hasOne = false;
        for (int j = left; j < right; j++) {
            if (matrix[top - 1][j] == 1) {
                hasOne = true;
                break;
            }
        }
        if (!hasOne) return false;
    }

    // Check if we can expand downward
    if (bottom < rows) {
        boolean hasOne = false;
        for (int j = left; j < right; j++) {
            if (matrix[bottom][j] == 1) {
                hasOne = true;
                break;
            }
        }
        if (!hasOne) return false;
    }

    // Check if we can expand leftward
    if (left > 0) {
        boolean hasOne = false;
        for (int i = top; i < bottom; i++) {
            if (matrix[i][left - 1] == 1) {
                hasOne = true;
                break;
            }
        }
        if (!hasOne) return false;
    }

    // Check if we can expand rightward
    if (right < cols) {
        boolean hasOne = false;
        for (int i = top; i < bottom; i++) {
            if (matrix[i][right] == 1) {
                hasOne = true;
                break;
            }
        }
        if (!hasOne) return false;
    }

    // Can't expand in any direction—this is a maximal rectangle
    return true;
}

Then, we'll write the main function to count all maximal rectangles, with some optimizations to avoid unnecessary checks:

static int countMaximalZeroRectangles(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return 0;
    }
    int rows = matrix.length;
    int cols = matrix[0].length;
    int count = 0;

    // Iterate all possible top-left corners
    for (int top = 0; top < rows; top++) {
        for (int left = 0; left < cols; left++) {
            // Skip if starting cell is 1—no all-zero rectangle can start here
            if (matrix[top][left] != 0) {
                continue;
            }

            // Iterate all possible heights (from 1 to remaining rows)
            for (int height = 1; height <= rows - top; height++) {
                int bottom = top + height;
                // If the bottom row's left cell is 1, taller heights will also include this 1—break early
                if (matrix[bottom - 1][left] != 0) {
                    break;
                }

                // Iterate all possible widths (from 1 to remaining columns)
                for (int width = 1; width <= cols - left; width++) {
                    int right = left + width;
                    // If the right column's top cell is 1, wider widths will also include this 1—break early
                    if (matrix[top][right - 1] != 0) {
                        break;
                    }

                    // Check if this subrectangle is all zeros
                    if (areAllZeros(matrix, top, left, height, width)) {
                        // Check if it's maximal
                        if (isMaximal(matrix, top, left, height, width)) {
                            count++;
                        }
                    } else {
                        // Wider widths will also have non-zero cells—break early
                        break;
                    }
                }
            }
        }
    }
    return count;
}

测试你的示例 #

Let's test this with your sample matrix:

public static void main(String[] args) {
    int[][] matrix = {
        {0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0}
    };
    System.out.println(countMaximalZeroRectangles(matrix)); // Output: 3
}

This will print 3, which matches your expected result.

注意事项 #

• This approach works well for small to medium-sized matrices. For very large matrices, you might want to look into more optimized algorithms (like using histogram-based methods to find all maximal rectangles in linear time relative to the matrix size), but this implementation is straightforward and easy to understand.
• Make sure to handle edge cases, like empty matrices or matrices with no zeros at all (which will return 0).

内容的提问来源于stack exchange，提问作者not_founded