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

Leetcode -598- Range summation

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

There is no address for the moment oh return, Monday to!

[Topic Introduction]

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]] output: 4: 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]]

Execute after the operation (3, 3], M = [[2, 2, 1], [2, 2, 1], [1, 1, 1]]

  • The largest integer in M is 2, and M has four elements of 2. So return 4.

Note:

  • The range of m and n is [1,40000].
  • The range of A is [1,m], and the range of B is [1,n].
  • The number of operations does not exceed 10,000.

Idea 1: Mathematical simulation

  • The easy ones are pretty easy
  • The function of the first analysis operation (x,y) is to add the point +1 in the rectangle with (0,0) and (x,y) as diagonal coordinates
  • That is, the number of points with the largest value after the operation is the area of the rectangle covered the most times
  • To make it easier for all arrays, you just have to get the minimum value of x and y
class Solution {
    public int maxCount(int m, int n, int[][] ops) {
            int minx  = m, miny = n;
            for(int [] op: ops){
                minx = Math.min(minx,op[0]);
                miny = Math.min(miny,op[1]);
            }
            returnminx * miny; }}Copy the code
  • Time complexity O(n), where n is the length of OPS
  • Space complexity O(1)