“This is the sixth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

The title

Given a matrix M of size m by n with zero initial elements and a series of update operations on m.

The operations are represented by a two-dimensional array, where each operation is represented by an array of two positive integers A and b. The implication is to increment the value of all elements M[I][j] that match 0 <= I < a and 0 <= j < b by one.

After performing a given set of operations, you need to return the number of elements in the matrix that contain the largest integer.

Example 1:

Input: m = 3, n = 3 operations = [[2,2],[3,3] Initial state, M = [[0, 0, 0], [0, 0, 0], [0, 0, 0]] execute after the operation (2, 2], M = [[1, 1, 0], [1, 1, 0], [0, 0, 0]] after [3, 3] after the operation, M = [[2, 2, 1], [2, 2, 1], [1, 1]] The largest integer in M is 2, and there are four elements in M with the value of 2. So return 4Copy the code

Thought analysis

You don’t even have to look at it to know that it’s prefix and difference, but suddenly notice the sentence given in the question

After performing a given set of operations, you need to return the number of elements in the matrix that contain the largest integer.

Find the smallest intersection given to a two-dimensional array (e.g. [1,1], [1,3], [3,1]).

Because of the monotony inherent in this problem, the element at position (0,0) will be incremented by 1 no matter what operation is performed, so every element with the smallest intersection must be an element that has occurred in any operation.

int maxCount(int m, int n, vector<vector<int>>& ops) {
        if (ops.size() = =0)return m * n;
        int xi = ops[0] [0], yi = ops[0] [1];
        for(int i = 0; i < ops.size(a); i++){int x = ops[i][0], y = ops[i][1];
            xi = min(x, xi);
            yi = min(y, yi);
        }
        return xi * yi;
    }
Copy the code

It’s ridiculous, you have to create an empty two-dimensional array card, and there is no one to force the buckle