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)``。