LeetCode Range Addition II

LeetCode Range Addition II

Given an m * n matrix M initialized with all 0's and several update operations.

Operations are represented by a 2D array, and each operation is represented by an array with two positive integers a and b, which means M[i][j] should be added by one for all 0 <= i < a and 0 <= j < b.

You need to count and return the number of maximum integers in the matrix after performing all the operations.

Example 1:

Input: 
m = 3, n = 3
operations = [[2,2],[3,3]]
Output: 4
Explanation: 
Initially, M = 
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

After performing [2,2], M = 
[[1, 1, 0],
 [1, 1, 0],
 [0, 0, 0]]

After performing [3,3], M = 
[[2, 2, 1],
 [2, 2, 1],
 [1, 1, 1]]

So the maximum integer in M is 2, and there are four of it in M. So return 4.

Note:

  1. The range of m and n is [1,40000].
  2. The range of a is [1,m], and the range of b is [1,n].
  3. The range of operations size won't exceed 10,000.

给定一个全为0的矩阵M,和一系列的操作,每个操作都是一对(a,b),表示要对所有i在[0,a)和j在[0,b)的元素M[i][j],问最终矩阵M中最大元素的个数。

这个题稍微想一下就会发现非常简单。

假设矩阵的左下角坐标为(0,0),对于某一个操作(a,b),表示把以(0,0)和(a,b)为对角顶点的子矩阵元素加1。那么(a1,b1)和(a2,b2)两个操作的重叠区域(0,0)-(a2,b1)所在子矩阵的元素就被加了两次,他们的值最大且相同。

Range Addition II

所以我们只需要遍历所有操作,分别找到行和列的最小值,则他们和原点围成的子矩阵的元素值最大,且相等。

代码非常简单,如下:

class Solution {
public:
	int maxCount(int m, int n, vector<vector<int>>& ops) {
		int minRow = m, minCol = n;
		for (const auto &op : ops) {
			minRow = min(minRow, op[0]);
			minCol = min(minCol, op[1]);
		}
		return minRow*minCol;
	}
};

本代码提交AC,用时6MS。

Leave a Reply

Your email address will not be published. Required fields are marked *