【Leetcode算法题】598. 范围求和II

By Long Luo

今天Leetcode的每日一题是:598. 范围求和 II,题目如下:

  1. 范围求和II

给定一个初始元素全部为0,大小为m×nm \times n的矩阵MM以及在MM上的一系列更新操作。

操作用二维数组表示,其中的每个操作用一个含有两个正整数a和b的数组表示,含义是将所有符合0 <= i < a以及0 <= j < b的元素M[i][j]的值都增加1。

在执行给定的一系列操作后,你需要返回矩阵中含有最大整数的元素个数。

示例 1:
输入:
m = 3, n = 3
operations = [[2,2],[3,3]]
输出: 4
解释:
初始状态, M =
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]

执行完操作[2,2]后, M =
[[1, 1, 0],
[1, 1, 0],
[0, 0, 0]]

执行完操作 [3,3] 后, M =
[[2, 2, 1],
[2, 2, 1],
[1, 1, 1]]

M中最大的整数是 2, 而且M中有4个值为2的元素。因此返回4。

注意:
m和n的范围是[1, 40000]。
a 的范围是[1, m],b 的范围是[1, n]。
操作数目不超过 10000。

方法一: 暴力

思路与算法:

这是一道简单题,很简单,我们先按照题意,将矩阵数字进行操作,最后遍历矩阵看看最大的数有几个即可。

而最大的值显然是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(kmn)O(kmn),其中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)