598. Range Addition II

Problem

You are given an m x n matrix M initialized with all 0’s and an array of operations ops, where ops[i] = [aᵢ, bᵢ] means M[x][y] should be incremented by one for all 0 <= x < aᵢ and 0 <= y < bᵢ.

Count and return the number of maximum integers in the matrix after performing all the operations.

https://leetcode.cn/problems/range-addition-ii/

Example 1:

Input: m = 3, n = 3, ops = [[2,2],[3,3]]
Output: 4
Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4.

Example 2:

Input: m = 3, n = 3, ops = [[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3]]
Output: 4

Example 3:

Input: m = 3, n = 3, ops = []
Output: 9

Constraints:

• 1 <= m, n <= 4 * 10⁴
• 0 <= ops.length <= 10⁴
• ops[i].length == 2
• 1 <= aᵢ <= m
• 1 <= bᵢ <= n

Test Cases

1
2

class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:

1
2
3
4
5
6
7
8
9
10
11
12
13

import pytest

from solution import Solution


@pytest.mark.parametrize('m, n, ops, expected', [
    (3, 3, [[2,2],[3,3]], 4),
    (3, 3, [[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3]], 4),
    (3, 3, [], 9),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, m, n, ops, expected):
    assert sol.maxCount(m, n, ops) == expected

Thoughts

如果 ops 为空，则初始的整个数组都是最大值（0），大小为 m * n。否则取 ops 中最小的 aᵢ 和最小的 bᵢ 围成的矩形，是每一次 op 都会执行加一操作的区域。

时间复杂度 O(m * n)，空间复杂度 O(1)。

Code

1
2
3
4
5
6
7
8
9
10

class Solution:
    def maxCount(self, m: int, n: int, ops: list[list[int]]) -> int:
        min2 = lambda a, b: a if a <= b else b
        height = m
        width = n
        for op in ops:
            height = min2(height, op[0])
            width = min2(width, op[1])

        return height * width

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章