区间加法 II
难度:
标签:
题目描述
You are given an m x n matrix M initialized with all 0's and an array of operations ops, where ops[i] = [ai, bi] means M[x][y] should be incremented by one for all 0 <= x < ai and 0 <= y < bi.
Count and return the number of maximum integers in the matrix after performing all the operations.
Example 1:
Input: m = 3, n = 3, ops = [[2,2],[3,3]] Output: 4 Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4.
Example 2:
Input: 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]] Output: 4
Example 3:
Input: m = 3, n = 3, ops = [] Output: 9
Constraints:
1 <= m, n <= 4 * 1040 <= ops.length <= 104ops[i].length == 21 <= ai <= m1 <= bi <= n
代码结果
运行时间: 22 ms, 内存: 17.4 MB
/*
* Using Java Stream API, the approach remains the same as the non-stream solution.
* We will use streams to find the minimum of the first and second elements in the ops array.
* The minimums will then be multiplied to get the count of the maximum integer.
*/
import java.util.Arrays;
public class Solution {
public int maxCount(int m, int n, int[][] ops) {
int minA = Arrays.stream(ops)
.mapToInt(op -> op[0])
.min()
.orElse(m);
int minB = Arrays.stream(ops)
.mapToInt(op -> op[1])
.min()
.orElse(n);
return minA * minB;
}
}解释
方法:
这个题解的思路是利用题目给定操作的特点来简化计算。根据题意，所有满足 0 <= x < ai 和 0 <= y < bi 的格子都会加 1。因此，经过所有操作后，最终矩阵中最大的整数一定出现在所有操作的交集区域内。我们只需要找出所有操作中最小的 ai 和最小的 bi，它们的乘积就是最大整数的个数。如果 ops 为空，说明没有任何操作，此时矩阵中所有元素都为0，最大整数的个数就是 m*n。
时间复杂度:
O(len(ops))
空间复杂度:
O(len(ops))
代码细节讲解
🦆
为什么算法在计算最小的 ai 和 bi 时，选择使用两个列表 L1 和 L2 来存储所有 ai 和 bi 的值，而不是在遍历过程中直接维护当前的最小值？
▷🦆
题解中提到如果 ops 数组为空，返回 m * n，但是否需要考虑 m 或 n 为 0 的特殊情况？如果 m 或 n 为 0，返回值应该是多少？
▷🦆
在实现中，每次操作都将 ai 和 bi 添加到列表中，这在操作数很大时会不会影响性能？是否有更优的方法来处理这个问题？
▷