題目
598. 范圍求和 II
給定一個初始元素全部為 0，大小為 m*n 的矩陣 M 以及在 M 上的一系列更新操作，
操作用二維陣串列示，其中的每個操作用一個含有兩個正整數 a 和 b 的陣串列示，含義是將所有符合 0 <= i < a 以及 0 <= j < b 的元素 M[i][j] 的值都增加 1，
在執行給定的一系列操作后，你需要回傳矩陣中含有最大整數的元素個數，
示例 1:
輸入:
m = 3, n = 3
operations = [[2,2],[3,3]]
輸出: 4
解釋:
初始狀態, M =
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
執行完操作 [2,2] 后, M =
[[1, 1, 0],
[1, 1, 0],
[0, 0, 0]]
執行完操作 [3,3] 后, M =
[[2, 2, 1],
[2, 2, 1],
[1, 1, 1]]
M 中最大的整數是 2, 而且 M 中有4個值為2的元素，因此回傳 4，
注意:
m 和 n 的范圍是 [1,40000]，
a 的范圍是 [1,m]，b 的范圍是 [1,n]，
運算元目不超過 10000，
解題思路
- 題目要求最后給出矩陣中最大整數的元素個數，
- 仔細一看，就是求交集（哪些元素經歷了多次的操作，）
- 因為如果后面的范圍比前面的范圍要大的話，前面的范圍是一定會執行的，那么前面的數字就是一定會發生改變的，也就是前面的元素一定是經歷了多次的操作，也就是交集，
Code
class Solution:
def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
for i, j in ops:
m = min(m, i)
n = min(n, j)
return m * n
運行結果
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/352143.html
標籤：其他
上一篇：LeetCode刷題day15