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 == 21 <= aᵢ <= m1 <= bᵢ <= n
Test Cases
class Solution:
def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int: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
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
评论需要 JavaScript。