0598. Range Addition II ======================= 题目信息 -------- :题号: 0598 :难度: Easy :主题: 矩阵、前缀矩形增量、最大值区域、操作交集 :原题: `LeetCode 0598 `_ :重点: 每次操作给左上前缀矩形全部加一、最大值出现在所有操作共同覆盖区域、无操作时全矩阵并列最大 题目重述 -------- 初始有一个 ``m × n`` 的整数矩阵,所有元素均为 ``0``。每个操作 ``[a, b]`` 会把所有满足 ``0 <= row < a`` 且 ``0 <= col < b`` 的格子加 ``1``。 执行全部操作后,返回矩阵中等于最大值的格子数量。若 ``ops`` 为空,所有格子仍都为 ``0`` 且并列最大,因此返回 ``m * n``。 自建示例 -------- 多个前缀矩形的共同覆盖区域: .. code-block:: text 输入:m = 4,n = 5,ops = [[3,4],[2,5],[4,2]] 输出:4 解释:每次操作都覆盖的区域是前 2 行、前 2 列,共有 2*2=4 个格子,它们获得最大增量 3。 没有操作: .. code-block:: text 输入:m = 2,n = 3,ops = [] 输出:6 解释:六个格子均保持为 0,全部等于矩阵最大值。 求所有操作矩形的共同左上区域 ---------------------------- 一次操作覆盖一个左上角固定为 ``(0, 0)`` 的前缀矩形。被所有操作覆盖的格子恰好获得最多增量,因此最大值区域的行数是所有 ``a`` 的最小值,列数是所有 ``b`` 的最小值;没有操作时,最小值仍为原矩阵的行数和列数。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int maxCount(int m, int n, std::vector>& ops) { int rows = m; int columns = n; for (const auto& operation : ops) { rows = std::min(rows, operation[0]); columns = std::min(columns, operation[1]); } return rows * columns; } }; 代码分析 -------- 每次操作都从同一个左上角开始,公共覆盖区域的尺寸由最短前缀决定,区域内每格都被全部操作命中,区域外至少少一次增量,故它们正好是全部最大值位置。只需扫描操作列表,时间复杂度为 ``O(k)``,额外空间复杂度为 ``O(1)``。