【LeetCode 每日一题】3195. 包含所有 1 的最小矩形面积 I——（解法二）边界追踪

Problem: 3195. 包含所有 1 的最小矩形面积 I

整体思路

这段代码同样旨在计算能够完全包围所有 ‘1’ 的最小矩形的面积。与上一个使用“投影”数组的版本相比，此实现采用了一种更直接的边界追踪方法，在单次遍历中直接确定矩形的四个边界，从而在空间上更为高效。

1. 核心思想：直接追踪四至边界

   • 算法的逻辑非常直接：最小包围矩形由四个值唯一确定——包含 ‘1’ 的最小行索引 (top)、最大行索引 (bottom)、最小列索引 (left) 和最大列索引 (right)。
   • 因此，算法的目标就是在一次遍历中找出这四个极值。

2. 初始化边界变量

   • top 和 left：被初始化为 Integer.MAX_VALUE。这是一个标准的寻找最小值的技巧。当遍历遇到第一个 ‘1’ 时，其行索引 i 和列索引 j 必然小于 MAX_VALUE，从而正确地设置初始的 top 和 left 边界。
   • bottom 和 right：被初始化为 0。这是为了寻找最大值。由于索引 i 和 j 都是非负的，这个初始化是安全的。

3. 单次遍历与边界更新

   • 算法通过一次完整的嵌套循环遍历 grid 的每一个单元格。
   • 当遇到一个值为 ‘1’ 的单元格 grid[i][j] 时，就用它的坐标 (i, j) 来尝试更新四个边界：
     • top = Math.min(top, i): 如果当前行 i 比已知的 top 更靠上（索引更小），则更新 top。
     • bottom = i: 一个巧妙的优化。由于外层循环 i 是单调递增的，所以每当在第 i 行找到一个 ‘1’，我们都可以暂时认为 i 是当前的 bottom。当循环结束时，bottom 最终的值必然是最后一个包含 ‘1’ 的行的索引，也就是最大行索引。使用 Math.max(bottom, i) 也能达到同样的效果，但直接赋值 bottom = i 更简洁。
     • left = Math.min(left, j): 如果当前列 j 比已知的 left 更靠左（索引更小），则更新 left。
     • right = Math.max(right, j): 如果当前列 j 比已知的 right 更靠右（索引更大），则更新 right。

4. 计算最终面积

   • 在遍历完整个矩阵后，top, bottom, left, right 四个变量就精确地定义了最小包围矩形的边界。
   • 矩形的高度是 bottom - top + 1（+1 是因为边界是包含的）。
   • 矩形的宽度是 right - left + 1。
   • 将两者相乘即可得到最终的面积。

完整代码

class Solution {
    /**
     * 计算能够包围 grid 中所有 '1' 的最小矩形的面积。
     * (直接边界追踪法)
     * @param grid 一个由 0 和 1 组成的二维整数数组
     * @return 最小包围矩形的面积
     */
    public int minimumArea(int[][] grid) {
        // left: 最小包围矩形的左边界（最小列索引）
        // 初始化为最大值，以确保第一个 '1' 的列索引能正确设置它
        int left = Integer.MAX_VALUE;
        // right: 最小包围矩形的右边界（最大列索引）
        int right = 0;
        // top: 最小包围矩形的上边界（最小行索引）
        // 初始化为最大值，以确保第一个 '1' 的行索引能正确设置它
        int top = Integer.MAX_VALUE;
        // bottom: 最小包围矩形的下边界（最大行索引）
        int bottom = 0;
        
        // 步骤 1: 单次遍历整个矩阵来寻找四个边界
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                // 如果当前单元格是 '1'
                if (grid[i][j] == 1) {
                    // 步骤 2: 更新四个边界值
                    // 更新上边界：取当前已知的 top 和当前行 i 中的较小者
                    top = Math.min(top, i);
                    // 更新下边界：由于 i 是递增的，最后一次遇到 '1' 的行 i 就是下边界
                    bottom = i;
                    // 更新左边界：取当前已知的 left 和当前列 j 中的较小者
                    left = Math.min(left, j);
                    // 更新右边界：取当前已知的 right 和当前列 j 中的较大者
                    right = Math.max(right, j);
                }
            }
        }
        
        // 步骤 3: 计算并返回面积
        // 高度 = bottom - top + 1 (因为边界是包含的，所以要+1)
        // 宽度 = right - left + 1
        return (bottom - top + 1) * (right - left + 1);
    }
}

时空复杂度

时间复杂度：O(m * n)

1. 循环：算法的核心是一个嵌套的 for 循环，它对 grid 矩阵进行了一次完整的线性扫描，访问了所有 m * n 个单元格。
2. 循环内部操作：
   • 在每次迭代中，执行的操作（if 判断、Math.min/Math.max、赋值）都是常数时间复杂度的，即 O(1)。

综合分析：
算法的总时间复杂度是 m * n 次 O(1) 操作，因此最终的时间复杂度为 O(m * n)。

空间复杂度：O(1)

1. 主要存储开销：该算法没有创建任何与输入规模 m 或 n 成比例的新的数据结构。
2. 辅助变量：只使用了 left, right, top, bottom, i, j 等几个固定数量的整型变量。

综合分析：
算法所需的额外辅助空间是常数级别的，不随输入矩阵的大小而变化。因此，其空间复杂度为 O(1)。这是解决此问题的最优空间复杂度。

参考灵神