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

By Long Luo

Leetcode 598. 范围求和 II。

方法一： 模拟

思路与算法：

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

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

代码如下所示：

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)$，需要创建一个新的二维数组。

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

思路与算法：

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

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

代码如下所示：

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. 😉😃💗