当前位置：首页 > article >正文

【Leetcode 每日一题】598. 区间加法 II

article 2025/2/3 22:42:50

问题背景

给你一个 $\times n$ 的矩阵 $M$ 和一个操作数组 $o p$ 。矩阵初始化时所有的单元格都为 $0$ 。 $ops[i] = [a_i, b_i]$ 意味着当所有的 $\le x \lt a_i$ 和 $\le y \lt b_i$ 时， $M [x] [y]$ 应该加 $1$ 。
在执行完所有操作后，计算并返回矩阵中最大整数的个数。

数据约束

$\le m, n \le 4 \times 10 ^ 4$
$\le ops.length \le 10 ^ 4$
$o p s [i] . l e n g t h = 2$
$\le a_i \le m$
$\le b_i \le n$

解题过程

自己在倒腾二维前缀和数组，实际上每次操作都可以看做在原来的基础上重叠一个新矩形，所有矩形的左上角固定。
这样一来，最大整数一定是重叠次数最多的交集部分，找到它的右下角就可以计算出结果了。

具体实现

class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        int minX = m;
        int minY = n;
        for (int[] op : ops) {
            minX = Math.min(minX, op[0]);
            minY = Math.min(minY, op[1]);
        }
        return minX * minY;
    }
}