[toc]
leetcode 598. 范围求和 II
题目描述
- 范围求和 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
本文由mdnice多平台发布
