What is the main pattern used in Delete Greatest Value in Each Row?

The problem primarily uses the array plus sorting pattern, where each row is sorted to efficiently pick maximums.

How do I handle multiple identical maximums in a row?

You can remove any one of the identical maximums, as the total sum remains the same, the key is to select a maximum per iteration.

What is the time complexity for this problem?

Sorting each row gives O(m * n log n), and iterating through all columns adds O(m * n), so overall time complexity is O(m * n log n).

Can I use a heap to solve this problem?

Yes, using a heap per row lets you efficiently track and remove the largest element in each iteration, which is helpful for larger matrices.

What common mistakes should I avoid?

Avoid forgetting column reduction after each iteration, not sorting rows upfront, and accidentally summing all row elements instead of only the maximums.

#2500

Easy

auto_awesome数组·排序

LeetCode 题解工作台

删除每行中的最大值

给你一个 m x n 大小的矩阵 grid ，由若干正整数组成。执行下述操作，直到 grid 变为空矩阵：从每一行删除值最大的元素。如果存在多个这样的值，删除其中任何一个。将删除元素中的最大值与答案相加。注意每执行一次操作，矩阵中列的数据就会减 1 。返回执行上述操作后的答案。示例 1…

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

题目描述

给你一个 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

lightbulb

解题思路

方法一：排序

由于每一次操作都是从每一行中删除最大值，然后取最大值加到答案中，因此我们可以先对每一行进行排序。

接下来遍历每一列，取每一列的最大值，然后将其加到答案中即可。

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

1

2

3

4

5

6

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

speed

复杂度分析

指标	值
时间	complexity is O(m * n log n) for sorting all rows and O(m * n) for iterative removal, resulting in O(m * n log n). Space complexity is O(1) extra if sorting in place, or O(m * n) if storing sorted copies.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Watch for off-by-one errors when columns shrink after each removal.
question_mark
Check if sorting each row up front reduces repeated maximum searches.
question_mark
Be aware that multiple identical maximums in a row can be removed in any order, the sum remains correct.

warning

常见陷阱

外企场景

error
Forgetting that the number of columns decreases each iteration leads to index errors.
error
Not sorting rows first can result in inefficient repeated maximum searches.
error
Adding all removed elements instead of only the current maximum per row will give wrong total.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Calculate sum of minimum values removed from each row instead of maximums.
arrow_right_alt
Apply the same operation but only on specific columns based on a condition.
arrow_right_alt
Handle rectangular matrices where rows have different lengths after removals.

help

常见问题

外企场景

继续练习

#2679 矩阵中的和 #2503 矩阵查询可获得的最大分数 #2593 标记所有元素后数组的分数