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.

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]]

比较简单，就是一个一个矩阵的堆叠，取值最大的位置就是小矩阵a和b最小的地方，数目就是a*b。

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    int (int m, int n, vector<vector<int>>& ops) {
        for(int it=0;it<ops.size();++it){
            m=min(ops[it][0],m);
            n=min(ops[it][1],n);
        }
        return m*n;
    }
};

1
2
3
4
5
6
7
8
9
10

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

~Thanks~
By 海天游草~~~2017.6.3