Range Addition II

https://leetcode.com/problems/range-addition-ii/description/

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

Operations are represented by a 2D array, and each operation is represented by an array with twopositiveintegersaandb, which means M[i][j]should be added by onefor 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.

Thoughts

每次把op[x][y]内的点加1, 求加的次数最多的点的数目. 那么op[x][y]中x, y最小的那些点会被多加一次, 而且这些点也会被其它op + 1.

Code

class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        if (ops.length == 0) {
            return m * n;
        }

        int row = Integer.MAX_VALUE, col = Integer.MAX_VALUE;
        for (int[] op : ops) {
            row = Math.min(row, op[0]);
            col = Math.min(col, op[1]);
        }

        return row * col;
    }
}

Analysis

时间复杂度O(N), N为ops长度.