2025-08-28：提取至多 K 个元素的最大总和。用go语言，给出一个 n 行 m 列的矩阵 grid，和一个长度为 n 的

福大大架构师每日一题

发布于 2025-12-18 10:49:17

690

2025-08-28：提取至多 K 个元素的最大总和。用go语言，给出一个 n 行 m 列的矩阵 grid，和一个长度为 n 的数组 limits，以及一个整数 k。你可以从矩阵中挑出至多 k 个格子的数值，但每一行第 i 行所选的格子数量不能超过 limits[i]。求在满足这些行限制与总体不超过 k 的前提下，所能取得的数值总和的最大可能值，并输出该最大和。

n == grid.length == limits.length。

m == grid[i].length。

1 <= n, m <= 500。

0 <= grid[i][j] <= 100000。

0 <= limits[i] <= m。

0 <= k <= min(n * m, sum(limits))。

输入：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 。

题目来自力扣3462。

分步骤描述过程：

1. 问题理解：
- • 有一个 n 行 m 列的矩阵 grid，每行有 m 个整数。
- • 一个长度为 n 的数组 limits，其中 limits[i] 表示第 i 行最多能选取的格子数量。
- • 整数 k 表示总共最多能选取的格子数量（全局限制）。
- • 目标：在满足每行选取数量不超过 limits[i] 且总选取数不超过 k 的前提下，选取尽可能大的数值，使得总和最大。
2. 直觉与策略：
- • 由于目标是总和最大，应该优先选取较大的数值。
- • 每行内部：为了最大化总和，应该优先选取该行中最大的那些数值（因为每行最多只能选 limits[i] 个）。
- • 全局：需要从所有行中选出最大的 k 个数值（但受限于每行最多只能贡献 limits[i] 个）。
3. 具体步骤：
- • 步骤1：对每行内部排序（降序）：
  - • 对于每一行 grid[i]，将其元素按从大到小排序（降序排序）。
  - • 这样，该行最大的 limits[i] 个数值就在前面（因为最多只能选 limits[i] 个，所以只关心前 limits[i] 大的数）。
- • 步骤2：收集所有候选数值：
  - • 从每一行中，取出前 limits[i] 大的数值（即排序后该行的前 limits[i] 个元素），并将它们全部加入一个大的列表 a 中。
  - • 注意：每行最多贡献 limits[i] 个数值，但实际可能少于 limits[i]（如果该行数值个数不足？但题目中 limits[i] <= m，所以不会不足）。
- • 步骤3：全局排序（降序）：
  - • 将列表 a 中的所有数值进行降序排序（从大到小）。
- • 步骤4：选取前 k 个最大的数值：
  - • 从全局降序排序后的列表 a 中，取出前 k 个数值（因为最多只能选 k 个），并求和。
- • 步骤5：返回总和：
  - • 将前 k 个数值的和作为结果返回。
4. 为什么这样做是正确的？：
- • 每行内部降序排序后取前 limits[i] 个：确保了每行贡献的候选数值都是该行可能的最大值（且不超过行限制）。
- • 将所有候选数值合并后降序排序取前 k 个：确保了全局选取的是最大的 k 个数值（同时隐含满足了行限制，因为每行最多只有 limits[i] 个数值在候选列表中）。
- • 注意：由于每行最多只能选 limits[i] 个，而候选列表 a 中每行恰好有 limits[i] 个数值（即该行最大的那些），所以从 a 中取前 k 个时，可能某行被取了多个（但不会超过 limits[i]，因为该行在 a 中只有 limits[i] 个数值），因此行限制自然满足。
5. 示例验证：
- • 示例：grid = [[5,3,7],[8,2,6]], limits = [2,2], k=3。
  - • 第一行降序排序后为 [7,5,3]，取前2个：[7,5]。
  - • 第二行降序排序后为 [8,6,2]，取前2个：[8,6]。
  - • 合并候选列表：a = [7,5,8,6]。
  - • 降序排序 a：[8,7,6,5]。
  - • 取前3个：8,7,6，和为 21（但注意：实际代码中取的是前3个，即8、7、6，但这里第一行贡献了7，第二行贡献了8和6，每行都不超过2个，且总数为3，满足条件）。

复杂度分析：

• 时间复杂度：
- • 对每行内部排序：每行排序的时间复杂度为 O(m log m)，共有 n 行，所以总时间为 O(n * m log m)。
- • 收集候选数值：需要遍历每行的前 limits[i] 个元素，总元素个数最多为 sum(limits)（但不超过 n * m）。
- • 对候选列表 a 排序：a 的长度最多为 sum(limits)（但不超过 n * m），所以排序时间为 O((n*m) log(n*m))。
- • 总体时间复杂度：O(n * m log m + (n*m) log(n*m))。由于 n 和 m 最大为500，所以 n*m 最大为250000，在可接受范围内。
• 额外空间复杂度：
- • 存储候选列表 a：最多需要 n * m 个元素（即 O(n*m)）。
- • 排序需要递归栈空间（但Go的排序一般是原地排序，不需要额外空间？但降序排序使用自定义比较函数可能有一些开销）。
- • 总体额外空间复杂度为 O(n*m)（用于存储候选列表）。

Go完整代码如下：

package main

import (
    "fmt"
    "slices"
)

func maxSum(grid [][]int, limits []int, k int) (ans int64) {
    a := []int{}
    cmp := func(a, b int)int { return b - a }
    for i, row := range grid {
        slices.SortFunc(row, cmp)
        a = append(a, row[:limits[i]]...)
    }
    slices.SortFunc(a, cmp)
    for _, x := range a[:k] {
        ans += int64(x)
    }
    return
}

func main() {
    grid := [][]int{{5, 3, 7}, {8, 2, 6}}
    limits := []int{2, 2}
    k := 3
    result := maxSum(grid, limits, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def max_sum(grid, limits, k):
    """
    grid: List[List[int]]
    limits: List[int]，长度应为 n（行数），若不足则缺省为 0
    k: int，总共最多取 k 个元素
    返回最大总和（整数）
    """
    candidates = []
    for i, row in enumerate(grid):
        lim = limits[i] if i < len(limits) else0
        if lim <= 0:
            continue
        # 取该行前 lim 个最大值（若 lim 大于行长度则取整行）
        top = sorted(row, reverse=True)[:min(lim, len(row))]
        candidates.extend(top)

    # 对所有候选按降序取前 k 个求和
    candidates.sort(reverse=True)
    return sum(candidates[:k])

if __name__ == "__main__":
    grid = [[5, 3, 7], [8, 2, 6]]
    limits = [2, 2]
    k = 3
    print(max_sum(grid, limits, k))