What is the core strategy to solve Sum in a Matrix efficiently?

Sort each row in descending order and iteratively remove the first element from each row, adding the maximum among them to the score.

Can I use a heap to optimize this problem?

Yes, maintaining the current maximum of row heads in a heap reduces repeated scanning and speeds up large inputs.

Why does row-wise sorting matter in Sum in a Matrix?

Sorting ensures that each operation correctly identifies the largest available numbers per row, which maximizes the final score.

What should I be careful about with empty rows?

Always check for empty rows when removing elements to avoid index errors and incorrect maximum selection.

How does this problem illustrate the Array plus Sorting pattern?

It combines row-wise array manipulation with sorting to efficiently track and compute the maximum values for score accumulation.

#2679

Medium

auto_awesome数组·排序

LeetCode 题解工作台

矩阵中的和

给你一个下标从 0 开始的二维整数数组 nums 。一开始你的分数为 0 。你需要执行以下操作直到矩阵变为空：矩阵中每一行选取最大的一个数，并删除它。如果一行中有多个最大的数，选择任意一个并删除。在步骤 1 删除的所有数字中找到最大的一个数字，将它添加到你的分数中。请你返回最后的分数。…

数组排序堆（优先队列）矩阵模拟

题目描述

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

矩阵中每一行选取最大的一个数，并删除它。如果一行中有多个最大的数，选择任意一个并删除。
在步骤 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 。

提示：

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

lightbulb

解题思路

方法一：排序

我们可以先遍历矩阵的每一行，将每一行排序。

接下来，遍历矩阵的每一列，找到每一列的最大值，将这些最大值相加即可。

时间复杂度 $O(m \times n \times \log n)$ ，空间复杂度 $(\log n)$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

1

2

3

4

5

6

class Solution:
    def matrixSum(self, nums: List[List[int]]) -> int:
        for row in nums:
            row.sort()
        return sum(map(max, zip(*nums)))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on sorting rows efficiently before starting iterative removal.
question_mark
Consider using a priority queue if the interviewer hints at optimizing repeated max searches.
question_mark
Be ready to explain why row-wise sorting ensures the maximum score.

warning

常见陷阱

外企场景

error
Forgetting to sort rows in descending order can lead to suboptimal score calculations.
error
Ignoring empty rows when collecting maximums may cause index errors.
error
Using nested loops to find the maximum in every iteration is inefficient for large matrices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the minimum score by always adding the minimum among removed row elements instead of the maximum.
arrow_right_alt
Allow diagonal or column-wise removals instead of only row-wise, changing the iteration pattern.
arrow_right_alt
Handle dynamic matrices where new rows can be appended during operations, requiring online maximum tracking.

help

常见问题

外企场景

继续练习

#2500 删除每行中的最大值 #2593 标记所有元素后数组的分数 #2503 矩阵查询可获得的最大分数