LeetCode 598. Range Addition II(范围相加 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:
- The range of
m
andn
is [1,40000]. - The range of
a
is [1,m
], and the range ofb
is [1,n
]. - The range of operations size won't exceed 10,000.
解法一
思路
注意到这里虽然是指定矩形的某一范围内数字全部增加1,但矩形的左上角顶点永远都是(0, 0)
,如下图所示。
想要求得最大数的个数,也就是要确定哪块区域是所有的矩形都覆盖到了的,从上图我们可以显然发现,面积最小的那块矩形是所有矩形都覆盖到了的,所以这题实际就是确定最小的那个矩形了,这个简单,找到最小的长和宽就好了。
Python
class Solution:
def maxCount(self, m, n, ops):
"""
:type m: int
:type n: int
:type ops: List[List[int]]
:rtype: int
"""
result_m = m
result_n = n
for op in ops:
result_m = min(result_m, op[0])
result_n = min(result_n, op[1])
return result_m * result_n
Java
public class Solution {
public int maxCount(int m, int n, int[][] ops) {
int resultM = m;
int resultN = n;
for (int[] op : ops) {
resultM = Math.min(resultM, op[0]);
resultN = Math.min(resultN, op[1]);
}
return resultM * resultN;
}
}
C++
class Solution {
public:
int maxCount(int m, int n, vector<vector<int>> &ops) {
int resultM = m;
int resultN = n;
for (const vector<int> &op : ops) {
resultM = min(resultM, op[0]);
resultN = min(resultN, op[1]);
}
return resultM * resultN;
}
};