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

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

思路

还没看到更好的思路。