0598. Range Addition II

题目信息

题号:

0598

难度:

Easy

主题:

矩阵、前缀矩形增量、最大值区域、操作交集

原题:

LeetCode 0598

重点:

每次操作给左上前缀矩形全部加一、最大值出现在所有操作共同覆盖区域、无操作时全矩阵并列最大

题目重述

初始有一个 m × n 的整数矩阵,所有元素均为 0。每个操作 [a, b] 会把所有满足 0 <= row < a 且 0 <= col < b 的格子加 1。

执行全部操作后,返回矩阵中等于最大值的格子数量。若 ops 为空,所有格子仍都为 0 且并列最大,因此返回 m * n。

自建示例

多个前缀矩形的共同覆盖区域:

输入:m = 4,n = 5,ops = [[3,4],[2,5],[4,2]]
输出:4
解释:每次操作都覆盖的区域是前 2 行、前 2 列,共有 2*2=4 个格子,它们获得最大增量 3。

没有操作:

输入:m = 2,n = 3,ops = []
输出:6
解释:六个格子均保持为 0,全部等于矩阵最大值。

求所有操作矩形的共同左上区域

一次操作覆盖一个左上角固定为 (0, 0) 的前缀矩形。被所有操作覆盖的格子恰好获得最多增量,因此最大值区域的行数是所有 a 的最小值,列数是所有 b 的最小值;没有操作时,最小值仍为原矩阵的行数和列数。

C++ 实现

class Solution {
public:
    int maxCount(int m, int n, std::vector<std::vector<int>>& 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)。