Medium

题目描述

给你一个下标从 0 开始的二维整数数组 nums。一开始你的分数为 0。你需要执行以下操作直到矩阵变为空：

  1. 从矩阵的每一行中，选择最大的那个数并移除它。在平局的情况下，你可以选择其中任何一个。
  2. 在第 1 步选出的所有数字中，选择最大的那个数，将它加到你的分数中。

返回最终的分数。

示例 1：

输入：nums = [[7,2,1],[6,4,2],[6,5,3],[3,2,1]]
输出：15
解释：第一次操作中，我们移除 7、6、6 和 3，然后将 7 加到分数中。
接下来移除 2、4、5 和 2，将 5 加到分数中。
最后移除 1、2、3 和 1，将 3 加到分数中。
因此，最终分数是 7 + 5 + 3 = 15。

示例 2：

输入：nums = [[1]]
输出：1
解释：我们移除 1 并将它加到答案中，返回 1。

约束条件：

  • 1 <= nums.length <= 300
  • 1 <= nums[i].length <= 500
  • 0 <= nums[i][j] <= 10³

解题思路

解题思路

这道题目的核心在于理解操作过程：每轮操作都是从每行选择最大值，然后在这些最大值中选择最大的加入分数。

方法一：排序模拟（推荐） 观察题目提示，我们可以将每行按降序排列。这样做的好处是：

  • 第一轮操作：每行第0列的元素就是各行最大值
  • 第二轮操作：每行第1列的元素就是各行剩余元素的最大值
  • 以此类推…

因此，问题转化为：对每行排序后，求每列的最大值之和。

方法二：优先队列模拟 也可以为每行维护一个最大堆，每次取出各行的最大值，然后找出其中最大的加入分数。但这种方法时间复杂度较高。

排序方法更直观高效，时间复杂度为 O(m×n×log n)，其中 m 是行数，n 是列数。空间复杂度为 O(1)（原地排序）。

代码实现

class Solution {
public:
    int matrixSum(vector<vector<int>>& nums) {
        // 对每行进行降序排序
        for (auto& row : nums) {
            sort(row.begin(), row.end(), greater<int>());
        }
        
        int score = 0;
        int cols = nums[0].size();
        
        // 遍历每一列，找出每列的最大值
        for (int j = 0; j < cols; j++) {
            int maxInCol = 0;
            for (int i = 0; i < nums.size(); i++) {
                maxInCol = max(maxInCol, nums[i][j]);
            }
            score += maxInCol;
        }
        
        return score;
    }
};

class Solution:
    def matrixSum(self, nums: List[List[int]]) -> int:
        # 对每行进行降序排序
        for row in nums:
            row.sort(reverse=True)
        
        score = 0
        cols = len(nums[0])
        
        # 遍历每一列，找出每列的最大值
        for j in range(cols):
            max_in_col = 0
            for i in range(len(nums)):
                max_in_col = max(max_in_col, nums[i][j])
            score += max_in_col
        
        return score

public class Solution {
    public int MatrixSum(int[][] nums) {
        // 对每行进行降序排序
        foreach (var row in nums) {
            Array.Sort(row, (a, b) => b.CompareTo(a));
        }
        
        int score = 0;
        int cols = nums[0].Length;
        
        // 遍历每一列，找出每列的最大值
        for (int j = 0; j < cols; j++) {
            int maxInCol = 0;
            for (int i = 0; i < nums.Length; i++) {
                maxInCol = Math.Max(maxInCol, nums[i][j]);
            }
            score += maxInCol;
        }
        
        return score;
    }
}

var matrixSum = function(nums) {
    // 对每行进行降序排序
    for (let row of nums) {
        row.sort((a, b) => b - a);
    }
    
    let score = 0;
    const cols = nums[0].length;
    
    // 遍历每一列，找出每列的最大值
    for (let j = 0; j < cols; j++) {
        let maxInCol = 0;
        for (let i = 0; i < nums.length; i++) {
            maxInCol = Math.max(maxInCol, nums[i][j]);
        }
        score += maxInCol;
    }
    
    return score;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m×n×log n)，其中 m 是行数，n 是列数。排序每行需要 O(n log n)，共 m 行
空间复杂度O(1)，原地排序，只使用常数额外空间