LeetCode 598. 区间加法 II

约 3 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 腾讯
标签
数组 数学

题目描述

✅ 598. 区间加法 II

image-20260929112503816

image-20260929112503935

题意分析

矩阵初始全为零，每次操作 [a, b] 给行下标小于 a、列下标小于 b 的格子加一。要求的是最终最大值出现了多少次，而不是最大值本身。

所有操作都覆盖左上角矩形，且行列范围都非空，因此左上角一定能收到每次增量。无需实际创建矩阵，只要找出哪些格子和它一样被全部操作覆盖。

解法：求所有操作的交集面积

核心思路

[!blue]
假设有 q 次操作，一个格子的最终值就是被覆盖的次数，最多为 q。全部操作的交集非空，其中每格都增加了 q 次；交集外的格子至少漏掉一次操作，值严格更小。因此最大值区域恰好就是所有操作的交集。

一个格子要被全部操作覆盖，行下标必须小于所有 a，列下标必须小于所有 b。所以交集是 [0, minRow) × [0, minCol)，其中两个边界分别取所有 a 和所有 b 的最小值，面积为 minRow * minCol。

两个最小边界可能来自不同操作，不能只找面积最小的一个操作。初始交集设为整张矩阵，即 minRow = m、minCol = n；没有操作时它仍是整张矩阵，所有零值都是最大值，答案自然为 m * n。

解题步骤

  1. 初始化最小行界 m、最小列界 n。
  2. 扫描每个操作，分别取两个维度的最小值。
  3. 返回最小行界与列界的乘积。

代码实现

class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        // 初值取 m、n：既是交集的单位元，也让空 ops 自然返回 m * n。
        int minRow = m;
        int minCol = n;

        for (int[] op : ops) {
            // 所有操作区域都锚定左上角，两个维度可以各自独立取最小。
            minRow = Math.min(minRow, op[0]);
            minCol = Math.min(minCol, op[1]);
        }

        // 交集内的格子被全部操作覆盖，取值最大；交集外至少少覆盖一次。
        return minRow * minCol;
    }
}

func maxCount(m int, n int, ops [][]int) int {
    // 初值取 m、n：既是交集的单位元，也让空 ops 自然返回 m * n。
    minRow := m
    minCol := n

    for _, op := range ops {
        // 所有操作区域都锚定左上角，两个维度可以各自独立取最小。
        if op[0] < minRow {
            minRow = op[0]
        }
        if op[1] < minCol {
            minCol = op[1]
        }
    }

    // 交集内的格子被全部操作覆盖，取值最大；交集外至少少覆盖一次。
    return minRow * minCol
}

复杂度分析

  • 时间复杂度：$O(q+1)$，q 为操作数。
  • 空间复杂度：$O(1)$。

关键点总结

[!green]

  • 答案是最大值区域的大小，不是操作次数。
  • 交集按两个维度独立取最小。
  • 空操作由全矩阵初值统一处理。

易错点总结

[!yellow]

  • 选面积最小的一个操作：它未必等于所有区域交集。
  • 取最大边界：计算成覆盖并集方向，不能表示全部同时覆盖。
  • a、b 当作闭区间下标：它们表示行列数量，不能再加一。
  • 初值取零：最小值将始终为零。

相似题目

题目 难度 关联与区别
223. 矩形面积 中等 同样计算轴对齐矩形的交集面积，本题所有操作都从原点出发，交集只需取最小行列上界。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/56432429
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！