[LeetCode]Range Addition II

综合技术 书影

题目描述:


LeetCode 598. Range Addition II

Given an m * n matrix M
initialized with all 0
‘s and several update operations.

Operations are represented by a 2D array, and each operation is represented by an array with two positive
integers a
and b
, which means M[i][j]
should be added by one
for all 0 <= i < a
and 0 <= j < b
.

You need to count and return the number of maximum integers in the matrix after performing all the operations.

Example 1:

Input: 
m = 3, n = 3
operations = [[2,2],[3,3]]
Output: 4
Explanation: 
Initially, M = 
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

After performing [2,2], M = 
[[1, 1, 0],
 [1, 1, 0],
 [0, 0, 0]]

After performing [3,3], M = 
[[2, 2, 1],
 [2, 2, 1],
 [1, 1, 1]]

So the maximum integer in M is 2, and there are four of it in M. So return 4.

Note:

  1. The range of m and n is [1,40000].
  2. The range of a is [1,m], and the range of b is [1,n].
  3. The range of operations size won’t exceed 10,000.

题目大意:

给定m * n矩阵M,初始为0,然后执行一些更新操作。

数组ops表示一组更新操作,每一个操作(a, b),表示将矩阵0 <= i < a 并且 0 <= j < b的区域值+1。

进行若干操作后,求矩阵的最大值。

注意:

  1. m和n的范围[1, 40000]
  2. a的范围[1, m],b的范围[1, n]
  3. 操作不超过10000个

解题思路:

求ops[0 .. len][0]和ops[0 .. len][1]的最小值

Python代码:

class Solution(object):
    def maxCount(self, m, n, ops):
        """
        :type m: int
        :type n: int
        :type ops: List[List[int]]
        :rtype: int
        """
        if not ops: return m * n
        return min(op[0] for op in ops) * min(op[1] for op in ops)
书影稿源:书影 (源链) | 关于 | 阅读提示

本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 综合技术 » [LeetCode]Range Addition II

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录