What is the main pattern used in Maximum Sum With at Most K Elements?

The main pattern is greedy choice plus invariant validation, ensuring each row limit is respected while maximizing the sum.

How do I handle row limits efficiently?

Sort each row descending and select only the top limits[i] elements, using a heap to combine rows efficiently.

What if k is smaller than the total available elements?

Use a max-heap to pick the k largest valid elements across all rows, always checking row limits.

Can elements be negative?

Yes, negative numbers can occur. The greedy strategy still works, but skip elements that would reduce the sum.

Is sorting necessary for this problem?

Yes, sorting each row descending is crucial to ensure the greedy selection chooses the largest available elements per row.

#3462

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

提取至多 K 个元素的最大总和

给你一个大小为 n x m 的二维矩阵 grid ，以及一个长度为 n 的整数数组 limits ，和一个整数 k 。你的目标是从矩阵 grid 中提取出至多 k 个元素，并计算这些元素的最大总和，提取时需满足以下限制：从 grid 的第 i 行提取的元素数量不超过 limits[i] 。返…

数组贪心排序堆（优先队列）矩阵

题目描述

给你一个大小为 n x m 的二维矩阵 grid ，以及一个长度为 n 的整数数组 limits ，和一个整数 k 。你的目标是从矩阵 grid 中提取出至多 k 个元素，并计算这些元素的最大总和，提取时需满足以下限制：

从 grid 的第 i 行提取的元素数量不超过 limits[i] 。

返回最大总和。

示例 1：

输入：grid = [[1,2],[3,4]], limits = [1,2], k = 2

输出：7

解释：

从第 2 行提取至多 2 个元素，取出 4 和 3 。
至多提取 2 个元素时的最大总和 4 + 3 = 7 。

示例 2：

输入：grid = [[5,3,7],[8,2,6]], limits = [2,2], k = 3

输出：21

解释：

从第 1 行提取至多 2 个元素，取出 7 。
从第 2 行提取至多 2 个元素，取出 8 和 6 。
至多提取 3 个元素时的最大总和 7 + 8 + 6 = 21 。

提示：

n == grid.length == limits.length
m == grid[i].length
1 <= n, m <= 500
0 <= grid[i][j] <= 10⁵
0 <= limits[i] <= m
0 <= k <= min(n * m, sum(limits))

lightbulb

解题思路

方法一：贪心 + 优先队列（小根堆）

我们可以用一个优先队列（小根堆） $\textit{pq}$ 来维护最大的 $k$ 个元素。

遍历每一行，对每一行的元素进行排序，然后取出每一行最大的 $\textit{limit}$ 个元素，将这些元素加入 $\textit{pq}$ 中。如果 $\textit{pq}$ 的大小超过了 $k$ ，就将堆顶元素弹出。

最后，将 $\textit{pq}$ 中的元素相加即可。

时间复杂度 $O(n \times m \times (\log m + \log k))$ ，空间复杂度 $O(k)$ 。其中 $n$ 和 $m$ 分别为矩阵 $\textit{grid}$ 的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxSum(self, grid: List[List[int]], limits: List[int], k: int) -> int:
        pq = []
        for nums, limit in zip(grid, limits):
            nums.sort()
            for _ in range(limit):
                heappush(pq, nums.pop())
                if len(pq) > k:
                    heappop(pq)
        return sum(pq)

speed

复杂度分析

指标	值
时间	complexity is O(n _m log m) for sorting plus O(k log n) for heap operations. Space complexity is O(n_ m) for the sorted rows and O(n) for the heap tracking candidates.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate quickly identifies greedy strategy for selecting maximum elements.
question_mark
Explains how row limits affect element selection and sum calculation.
question_mark
Uses sorting and heap to optimize selection while respecting constraints.

warning

常见陷阱

外企场景

error
Forgetting to enforce row limits and selecting more elements than allowed from a row.
error
Not handling k less than total selectable elements, leading to incorrect sum.
error
Ignoring the need to sort rows, which can lead to suboptimal greedy picks.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow negative integers in the grid, requiring careful top-k selection with possible pruning.
arrow_right_alt
Change the problem to select exactly k elements, which may require dynamic programming.
arrow_right_alt
Use a 3D matrix with per-layer limits, extending the greedy plus invariant validation pattern.

help

常见问题

外企场景

继续练习

#2931 购买物品的最大开销 #3362 零数组变换 III #3572 选择不同 X 值三元组使 Y 值之和最大