Easy

题目描述

给你一个由正整数组成的 m x n 矩阵 grid。

执行下述操作，直到 grid 变为空矩阵：

  • 从每一行删除值最大的元素。如果存在多个这样的值，删除其中任何一个。
  • 将删除元素中的最大值添加到答案中。

注意 每执行一次上述操作，列的数量都会减 1。

返回执行上述操作后的答案。

示例 1：

输入：grid = [[1,2,4],[3,3,1]]
输出：8
解释：上图展示了每一步中删除的值。
- 第一步操作中，我们从第一行删除 4 ，从第二行删除 3（注意，有两个单元格的值为 3 ，我们可以删除任意一个）。在答案上加 4 。
- 第二步操作中，我们从第一行删除 2 ，从第二行删除 3 。在答案上加 3 。
- 第三步操作中，我们从第一行删除 1 ，从第二行删除 1 。在答案上加 1 。
最终答案 = 4 + 3 + 1 = 8 。

示例 2：

输入：grid = [[10]]
输出：10
解释：上图展示了每一步中删除的值。
- 第一步操作中，我们从第一行删除 10 。在答案上加 10 。
最终答案 = 10 。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 1 <= grid[i][j] <= 100

解题思路

这道题的核心思路是模拟删除过程。我们需要在每轮操作中找到每行的最大值，然后取这些最大值中的最大值加入答案。

解法一：排序法（推荐） 最直观的方法是对每行进行排序，这样每行的最大值就在末尾。每次操作时，我们取每行的最后一个元素（最大值），找出其中的最大值累加到答案中，然后从每行移除最后一个元素。

解法二：堆/优先队列法 可以为每行维护一个最大堆，每次取堆顶元素参与比较。

解法三：暴力模拟法 每次遍历矩阵找每行最大值，然后标记为已删除。

从效率角度看，排序法是最简洁高效的。由于每行只需排序一次，后续操作都是 O(1) 的取值，整体复杂度较优。而且代码实现简单，不容易出错。

具体实现时，我们先对每行进行降序排序，然后进行 n 轮操作（n 为列数）。每轮从每行取第一个元素找最大值，然后删除这些元素。

代码实现

class Solution {
public:
    int deleteGreatestValue(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        // 对每一行进行降序排序
        for (int i = 0; i < m; i++) {
            sort(grid[i].begin(), grid[i].end(), greater<int>());
        }
        
        int answer = 0;
        // 执行n轮操作
        for (int col = 0; col < n; col++) {
            int maxVal = 0;
            // 找出当前轮次每行最大值中的最大值
            for (int row = 0; row < m; row++) {
                maxVal = max(maxVal, grid[row][col]);
            }
            answer += maxVal;
        }
        
        return answer;
    }
};

class Solution:
    def deleteGreatestValue(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # 对每一行进行降序排序
        for i in range(m):
            grid[i].sort(reverse=True)
        
        answer = 0
        # 执行n轮操作
        for col in range(n):
            max_val = 0
            # 找出当前轮次每行最大值中的最大值
            for row in range(m):
                max_val = max(max_val, grid[row][col])
            answer += max_val
        
        return answer

public class Solution {
    public int DeleteGreatestValue(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        
        // 对每一行进行降序排序
        for (int i = 0; i < m; i++) {
            Array.Sort(grid[i], (a, b) => b.CompareTo(a));
        }
        
        int answer = 0;
        // 执行n轮操作
        for (int col = 0; col < n; col++) {
            int maxVal = 0;
            // 找出当前轮次每行最大值中的最大值
            for (int row = 0; row < m; row++) {
                maxVal = Math.Max(maxVal, grid[row][col]);
            }
            answer += maxVal;
        }
        
        return answer;
    }
}

var deleteGreatestValue = function(grid) {
    const m = grid.length, n = grid[0].length;
    
    // 对每一行进行降序排序
    for (let i = 0; i < m; i++) {
        grid[i].sort((a, b) => b - a);
    }
    
    let answer = 0;
    // 执行n轮操作
    for (let col = 0; col < n; col++) {
        let maxVal = 0;
        // 找出当前轮次每行最大值中的最大值
        for (let row = 0; row < m; row++) {
            maxVal = Math.max(maxVal, grid[row][col]);
        }
        answer += maxVal;
    }
    
    return answer;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(m×n×log n)对m行分别排序需要O(m×n×log n)，后续n轮操作每轮O(m)，总计O(m×n×log n)
空间复杂度O(1)只使用常量额外空间，原地排序

相关题目