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

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 1 分钟

By Long Luo

Leetcode 598. 范围求和 II。

方法一： 模拟

思路与算法：

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

而最大的值显然是 \(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(km^2n^2)\)，其中 \(k\) 是数组 \(\textit{ops}\) 的长度。
  • 空间复杂度：\(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)\)，其中 \(k\) 是数组 \(\textit{ops}\) 的长度。
  • 空间复杂度：\(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. 😉😃💗