【C++刷题】力扣-#598-区间加法 II

题目描述

给你一个 m x n 的矩阵 M和一个操作数组 op 。矩阵初始化时所有的单元格都为 0 。ops[i] = [ai, bi]
意味着当所有的 0 <= x < ai 和 0 <= y < bi 时， M[x][y] 应该加 1。 在 执行完所有操作后 ，计算并返回
矩阵中最大整数的个数 。

示例

示例 1

输入: m = 3, n = 3，ops = [[2,2],[3,3]]
输出: 4
解释: M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。

示例 2

输入: m = 3, n = 3, ops = [[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3]]
输出: 4

示例 3

输入: m = 3, n = 3, ops = []
输出: 9

题解

1.初始化计数器：由于所有的操作都是增加1，我们只需要跟踪每个操作影响的单元格数量。
2.执行操作：对于每个操作 ops[i] = [ai, bi]，我们增加从第0行到第 ai-1 行和第0列到第 bi-1 列的单元格数量。这意味着我们只需要考虑操作影响的行数和列数。
3.计算最大整数的个数：在执行完所有操作后，矩阵中最大的整数将是所有操作中最小的行影响数和列影响数。然后，我们计算这个最大整数在矩阵中出现的次数，这将是所有行和列的最小影响数的乘积。

代码实现

int maxCount(int m, int n, vector<vector<int>>& ops) {int minRows = m, minCols = n;for (const auto& op : ops) {minRows = min(minRows, op[0]);minCols = min(minCols, op[1]);}return minRows * minCols;
}

复杂度分析

● 时间复杂度：O(k)，其中 k 是操作的数量。我们只需要一次遍历操作数组即可找到最小的行影响数和列影响数。
● 空间复杂度：O(1)，我们只使用了常数个额外变量。
这个算法的优势在于它避免了构建和操作整个矩阵的复杂性，而是通过简单的数学计算来解决问题。