wordpress 一键建站长沙seo免费诊断
题目描述
给你一个 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)，我们只使用了常数个额外变量。
这个算法的优势在于它避免了构建和操作整个矩阵的复杂性，而是通过简单的数学计算来解决问题。