[Leetcode][598. 范围求和 II] 求所有操作的交集

By Long Luo

Leetcode 598. 范围求和 II

方法一: 模拟

思路与算法:

首先按照题意,对矩阵进行操作,最后遍历矩阵看最大的数有几个即可。

而最大的值显然是 M[0][0]M[0][0]

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int maxCount(int m, int n, int[][] ops) {
if (ops == null || ops.length == 0 || ops[0].length == 0) {
return m * n;
}

int ans = 0;
int[][] mat = new int[m][n];
for (int[] op : ops) {
int row = op[0];
int col = op[1];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
mat[i][j]++;
}
}
}

int maxVal = mat[0][0];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (maxVal == mat[i][j]) {
ans++;
}
}
}

return ans;
}

复杂度分析

  • 时间复杂度:O(km2n2)O(km^2n^2),其中 kk 是数组 ops\textit{ops} 的长度。
  • 空间复杂度:O(mn)O(mn),需要创建一个新的二维数组。

方法二: 找到所有操作的交集

思路与算法:

方法一显然会超时,而且因为我们只需要找到最大值的个数,而有满足要求的次数恰好等于操作次数的位置。

我们只需要找到所有操作中的最小值。

代码如下所示:

1
2
3
4
5
6
7
8
9
10
public int maxCount(int m, int n, int[][] ops) {
int minRow = m;
int minCol = n;
for (int[] op : ops) {
minRow = Math.min(minRow, op[0]);
minCol = Math.min(minCol, op[1]);
}

return minRow * minCol;
}

复杂度分析

  • 时间复杂度:O(k)O(k),其中 kk 是数组 ops\textit{ops} 的长度。
  • 空间复杂度:O(1)O(1)

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗