Easy

题目描述

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

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

示例 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 * 10^4
  • 0 <= ops.length <= 10^4
  • ops[i].length == 2
  • 1 <= ai <= m
  • 1 <= bi <= n

解题思路

这道题需要理解操作的本质。每个操作 [ai, bi] 会对矩阵的左上角子矩阵（从 (0,0) 到 (ai-1, bi-1)）中的所有元素加 1。

关键观察：最大值出现的位置一定是所有操作区域的交集。因为交集区域的每个位置都被所有操作覆盖，所以这些位置的值最大。

具体思路：

  1. 如果没有操作，整个矩阵都是 0，最大值个数是 m * n
  2. 如果有操作，找到所有操作区域的交集
  3. 交集的行范围是所有 ai 的最小值，列范围是所有 bi 的最小值
  4. 交集的面积就是最大值的个数

举例说明：对于 ops = [[2,2], [3,3]]

  • 第一个操作覆盖 (0,0) 到 (1,1)，4个位置
  • 第二个操作覆盖 (0,0) 到 (2,2)，9个位置
  • 交集是 (0,0) 到 (1,1)，4个位置，这些位置值为 2（最大）

算法：遍历所有操作，记录最小的行数和列数，相乘得到答案。时间复杂度 O(k)，k 是操作数；空间复杂度 O(1)。

代码实现

class Solution {
public:
    int maxCount(int m, int n, vector<vector<int>>& ops) {
        if (ops.empty()) {
            return m * n;
        }
        
        int minRow = m, minCol = n;
        for (const auto& op : ops) {
            minRow = min(minRow, op[0]);
            minCol = min(minCol, op[1]);
        }
        
        return minRow * minCol;
    }
};

class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
        if not ops:
            return m * n
        
        min_row = min(op[0] for op in ops)
        min_col = min(op[1] for op in ops)
        
        return min_row * min_col

public class Solution {
    public int MaxCount(int m, int n, int[][] ops) {
        if (ops.Length == 0) {
            return m * n;
        }
        
        int minRow = m, minCol = n;
        foreach (var op in ops) {
            minRow = Math.Min(minRow, op[0]);
            minCol = Math.Min(minCol, op[1]);
        }
        
        return minRow * minCol;
    }
}

/**
 * @param {number} m
 * @param {number} n
 * @param {number[][]} ops
 * @return {number}
 */
var maxCount = function(m, n, ops) {
    if (ops.length === 0) return m * n;
    
    let minRow = m;
    let minCol = n;
    
    for (let op of ops) {
        minRow = Math.min(minRow, op[0]);
        minCol = Math.min(minCol, op[1]);
    }
    
    return minRow * minCol;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(k)k 是操作数组的长度，需要遍历所有操作
空间复杂度O(1)只使用常数额外空间

相关题目