0%

range-addition-ii

Range Addition II – LeetCode 598

Problem

Description

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.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int maxCount(int m, int n, vector<vector<int>>& ops) {
int Minx = m, Miny = n;
for(auto &i : ops){
Minx = min(Minx, i[0]);
Miny = min(Miny, i[1]);
}
return Minx * Miny;
}
};

思路

简单的贪心,可以将x和y轴分解开来分别看待。时间复杂度$O(n)$,空间复杂度$O(1)$。
耗时$4$ ms,排名$0.0\%$

Better

思路

还没看到更好的思路。