Medium

题目描述

给你一个整数 n 和一个下标从 0 开始的二维数组 queries ，其中 queries[i] = [typei, indexi, vali] 。

一开始，给你一个下标从 0 开始的 n x n 矩阵，所有元素均为 0 。每一个查询，你需要执行以下操作之一：

  • 如果 typei == 0 ，将第 indexi 行 的所有元素变为 vali ，覆盖任何之前的值。
  • 如果 typei == 1 ，将第 indexi 列 的所有元素变为 vali ，覆盖任何之前的值。

请你返回执行完所有查询后，矩阵中所有整数的和。

示例 1：

输入：n = 3, queries = [[0,0,1],[1,2,2],[0,2,3],[1,0,4]]
输出：23
解释：上图描述了每个查询以后矩阵的状态。所有查询执行完以后，矩阵元素之和为 23 。

示例 2：

输入：n = 3, queries = [[0,0,4],[0,1,2],[1,0,1],[0,2,3],[1,2,1]]
输出：17
解释：上图描述了每个查询以后矩阵的状态。所有查询执行完以后，矩阵元素之和为 17 。

提示：

  • 1 <= n <= 10^4
  • 1 <= queries.length <= 5 * 10^4
  • queries[i].length == 3
  • 0 <= typei <= 1
  • 0 <= indexi < n
  • 0 <= vali <= 10^5

解题思路

这道题的关键在于理解操作的覆盖性质。由于后面的操作会覆盖前面的操作结果，我们需要逆序处理查询。

核心思路：

  1. 逆序遍历：从最后一个查询开始处理，这样能确保我们处理的是每个位置的最终值
  2. 记录已处理的行列：使用集合记录已经被操作过的行和列，避免重复计算
  3. 计算贡献：当遇到一个未处理过的行/列操作时：
    • 行操作：影响该行中所有未被列操作覆盖的位置，贡献为 val × (n - 已处理列数)
    • 列操作：影响该列中所有未被行操作覆盖的位置，贡献为 val × (n - 已处理行数)

为什么逆序有效？

  • 最后执行的操作具有最高优先级，不会被覆盖
  • 一旦某行/列被处理过，之前对该行/列的操作都无效
  • 通过逆序遍历，我们能准确计算每个操作对最终结果的实际贡献

时间复杂度O(m)，空间复杂度O(n)，其中m为查询数量。

代码实现

class Solution {
public:
    long long matrixSumQueries(int n, vector<vector<int>>& queries) {
        unordered_set<int> seenRows, seenCols;
        long long sum = 0;
        
        for (int i = queries.size() - 1; i >= 0; i--) {
            int type = queries[i][0], index = queries[i][1], val = queries[i][2];
            
            if (type == 0) { // 行操作
                if (seenRows.find(index) == seenRows.end()) {
                    seenRows.insert(index);
                    sum += (long long)val * (n - seenCols.size());
                }
            } else { // 列操作
                if (seenCols.find(index) == seenCols.end()) {
                    seenCols.insert(index);
                    sum += (long long)val * (n - seenRows.size());
                }
            }
        }
        
        return sum;
    }
};

class Solution:
    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:
        seen_rows = set()
        seen_cols = set()
        total_sum = 0
        
        for type_val, index, val in reversed(queries):
            if type_val == 0:  # 行操作
                if index not in seen_rows:
                    seen_rows.add(index)
                    total_sum += val * (n - len(seen_cols))
            else:  # 列操作
                if index not in seen_cols:
                    seen_cols.add(index)
                    total_sum += val * (n - len(seen_rows))
        
        return total_sum

public class Solution {
    public long MatrixSumQueries(int n, int[][] queries) {
        HashSet<int> seenRows = new HashSet<int>();
        HashSet<int> seenCols = new HashSet<int>();
        long sum = 0;
        
        for (int i = queries.Length - 1; i >= 0; i--) {
            int type = queries[i][0], index = queries[i][1], val = queries[i][2];
            
            if (type == 0) { // 行操作
                if (!seenRows.Contains(index)) {
                    seenRows.Add(index);
                    sum += (long)val * (n - seenCols.Count);
                }
            } else { // 列操作
                if (!seenCols.Contains(index)) {
                    seenCols.Add(index);
                    sum += (long)val * (n - seenRows.Count);
                }
            }
        }
        
        return sum;
    }
}

var matrixSumQueries = function(n, queries) {
    let rowSet = new Set();
    let colSet = new Set();
    let sum = 0;
    
    for (let i = queries.length - 1; i >= 0; i--) {
        let [type, index, val] = queries[i];
        
        if (type === 0) {
            if (!rowSet.has(index)) {
                rowSet.add(index);
                sum += val * (n - colSet.size);
            }
        } else {
            if (!colSet.has(index)) {
                colSet.add(index);
                sum += val * (n - rowSet.size);
            }
        }
    }
    
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(m)，其中 m 为查询数量，需要遍历所有查询一次
空间复杂度O(n)，最坏情况下需要存储所有行和列的索引

相关题目