leetcode 598. 范围求和 II

leetcode 598. 范围求和 II

题目描述

598. 范围求和 II

给你一个 m x n 的矩阵 M ，初始化时所有的 0 和一个操作数组 op ，其中 ops[i] = [ai, bi] 意味着当所有的 0 <= x < ai 和 0 <= y < bi 时， M[x][y] 应该加 1。

在 执行完所有操作后 ，计算并返回 矩阵中最大整数的个数 。

示例 1:

输入: m = 3, n = 3，ops = [[2,2],[3,3]] 输出: 4 解释: M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。 示例 2:

输入: 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]] 输出: 4 示例 3:

输入: m = 3, n = 3, ops = [] 输出: 9

提示:

1 <= m, n <= 4 * 104 0 <= ops.length <= 104 ops[i].length == 2 1 <= ai <= m 1 <= bi <= n

解题思路

法1

模拟:横向最小值与纵向最小值\

由题意可知我们需要得到横纵坐标相乘最小的值,但是我们必须考虑到交叉的情况

例如:3;3[1,2][2,1]

结果:

2,1,0

1,0,0

0,0,0

最大值为2,只有一个,所以应该输出1

• 时间复杂度(O(n))
• 空间复杂度(O(1))

执行结果

法1

func maxCount(m int, n int, ops [][]int) int {
 if len(ops) == 0 {
  return m * n
 }
 l1, l2 := ops[0][0], ops[0][1]
 for i := 1; i < len(ops); i++ {
  if ops[i][0] < l1 {//横坐标最小值
   l1 = ops[i][0]
  }
  if ops[i][1] < l2 {//纵坐标最小值
   l2 = ops[i][1]
  }
 }
 return l1 * l2
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 4 ms , 在所有 Go 提交中击败了 94.64% 的用户 内存消耗： 3.6 MB , 在所有 Go 提交中击败了 89.29% 的用户 通过测试用例： 69 / 69 炫耀一下:

法2

法3