This is the 7th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.

Topic describes

This is 598 on LeetCode. Scope sum II, easy difficulty.

Tag: “Simulation”

Given a matrix MMM whose initial elements are all 000 and whose size is M ∗nm*nm∗n, and a series of update operations on MMM.

Operations are represented by two-dimensional arrays, where each operation is represented by an array containing two positive integers, AAA and BBB, Meaning is all in line with the 0 < = I < a0 < = I < a0 < = I < < b0 a and 0 < = j < = j < b0 < = j < b elements M [j] [I] M [j] [I] M [I] [j] values increase $14.

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 4.Copy the code

Note:

  • The range of MMM and NNN is [1 40000][1 40000].
  • Aaa is [m] 1, the range of [1, m] [m] 1, and the scope of the BBB is [1, n] [1, n] [1, n).
  • The number of operations does not exceed 100001000010000.

simulation

Since 0≤ I

The question becomes: what range of numbers is equal to the value at position (0,0)(0, 0)(0,0), that is, what range is covered by each operation.

It is not difficult to find that the area formed by the horizontal and vertical coordinates (x,y)(x, y)(x,y) in all OPS [I] OPS [I] and the upper left corner (0,0)(0, 0) can be guaranteed to be covered by each operation. X ∗yx * yx∗y is the answer.

Code:

class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        for (int[] op : ops) {
            m = Math.min(m, op[0]);
            n = Math.min(n, op[1]);
        }
        returnm * n; }}Copy the code
  • Time complexity: let KKK be the length of the OpSOPsOPS array. The complexity is O(k)O(k)O(k)
  • Space complexity: O(1)O(1)O(1)

The last

This is the No.598 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks, we will first finish all the topics without locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.