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
本文由多平台发布
下一篇：
基于SpringBoot搭建SSM项目