剑指Offer|LCR 040.最大矩形

LCR 040.最大矩形

输入：matrix = ["10100","10111","11111","10010"]
输出：6
解释：最大矩形如上图所示。

输入：matrix = []
输出：0

输入：matrix = ["0"]
输出：0

输入：matrix = ["1"]
输出：1

输入：matrix = ["00"]
输出：0

法1：暴力

分析：

遍历矩形的起始行列，结束行列。判断是否有0，有则标记false。

时间复杂度：$O(n^4)$

空间复杂度：$O(n^2)$

var maximalRectangle = function(matrix) {
    if (matrix.length === 0 || matrix[0].length === 0) {
            return 0;
        }

    const rows = matrix.length;
    const cols = matrix[0].length;
    let maxArea = 0;

    // 遍历所有的矩形区域
    for (let r1 = 0; r1 < rows; r1++) {  // 矩形的上边界
        for (let r2 = r1; r2 < rows; r2++) {  // 矩形的下边界
            for (let c1 = 0; c1 < cols; c1++) {  // 矩形的左边界
                for (let c2 = c1; c2 < cols; c2++) {  // 矩形的右边界
                    let isValid = true;

                    // 检查该矩形是否只包含 1
                    for (let r = r1; r <= r2; r++) {
                        for (let c = c1; c <= c2; c++) {
                            if (matrix[r][c] === '0') {
                                isValid = false;
                                break;
                            }
                        }
                        if (!isValid) break;
                    }

                    // 如果是有效的矩形，则计算面积并更新最大面积
                    if (isValid) {
                        const area = (r2 - r1 + 1) * (c2 - c1 + 1);
                        maxArea = Math.max(maxArea, area);
                    }
                }
            }
        }
    }

    return maxArea;
};

法2：栈

分析：

看例子：matrix = ["10100","10111","11111","10010"]

1. 初始化 heights 数组：
   • 第0行：heights = [1, 0, 1, 0, 0]
   • 第1行：heights = [2, 0, 2, 1, 1]
   • 第2行：heights = [3, 0, 3, 2, 2]
   • 第3行：heights = [1, 0, 4, 0, 3]
2. 调用 largestRectangleArea 计算每一行的最大矩形面积：
   • 第一行：heights = [1, 0, 1, 0, 0] 最大矩形面积为 1。
   • 第二行：heights = [2, 0, 2, 1, 1] 最大矩形面积为 2。
   • 第三行：heights = [3, 0, 3, 2, 2] 最大矩形面积为 6。
   • 第四行：heights = [1, 0, 4, 0, 3] 最大矩形面积为 4。

时间复杂度：$O(n^2)$

空间复杂度：$O(n)$

var maximalRectangle = function(matrix) {
 if (matrix.length === 0 || matrix[0].length === 0) {
        return 0;
    }

    const heights = new Array(matrix[0].length).fill(0);
    let maxArea = 0;

    for (let row of matrix) {
        for (let i = 0; i < row.length; i++) {
            if (row[i] === '0') {
                heights[i] = 0;
            } else {
                heights[i]++;
            }
        }

        maxArea = Math.max(maxArea, largestRectangleArea(heights));
    }

    return maxArea;
};


function largestRectangleArea(heights) {
    const stack = [-1]; // 初始栈包含 -1，用于计算宽度时的边界
    let maxArea = 0;

    for (let i = 0; i < heights.length; i++) {
        while (stack[stack.length - 1] !== -1 && heights[stack[stack.length - 1]] >= heights[i]) {
            const height = heights[stack.pop()];
            const width = i - stack[stack.length - 1] - 1;
            maxArea = Math.max(maxArea, height * width);
        }

        stack.push(i);
    }

    // 处理剩余栈中的元素
    while (stack[stack.length - 1] !== -1) {
        const height = heights[stack.pop()];
        const width = heights.length - stack[stack.length - 1] - 1;
        maxArea = Math.max(maxArea, height * width);
    }

    return maxArea;
}