Medium

题目描述

给你一个大小为 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 个元素。取出的元素是 4 和 3。
最多 2 个选中元素的最大可能和是 4 + 3 = 7。

示例 2：

输入：grid = [[5,3,7],[8,2,6]], limits = [2,2], k = 3
输出：21
解释：
从第一行，我们可以最多取 2 个元素。取出的元素是 7。
从第二行，我们可以最多取 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^5
  • 0 <= limits[i] <= m
  • 0 <= k <= min(n * m, sum(limits))

解题思路

解题思路

这是一道贪心算法题，关键在于如何从有限制的行中选择最大的 k 个元素。

核心思路：

  1. 预处理：对每行按降序排序，然后取前 limits[i] 个元素，这样每行都只保留可选的最大元素
  2. 全局最优选择：将所有可选元素放入一个最大堆中，然后贪心地选择最大的 k 个元素

具体步骤：

  1. 遍历每一行，将该行排序后取前 limits[i] 个最大元素
  2. 将所有可选元素加入优先队列（最大堆）
  3. 从堆中依次取出最大的 k 个元素求和

为什么这样做是正确的？

  • 因为我们要求最大和，所以应该优先选择较大的数
  • 每行的限制是独立的，所以先在行内选择最大的元素
  • 然后在所有可选元素中全局选择最大的 k 个

时间复杂度分析：

  • 排序：O(n × m log m)
  • 建堆：O(总元素数)
  • 取 k 个元素：O(k log(总元素数))

这种方法简单直观，符合贪心算法的思想。

代码实现

class Solution {
public:
    long long maxSum(vector<vector<int>>& grid, vector<int>& limits, int k) {
        priority_queue<int> pq;
        
        // 对每行排序并取前limits[i]个最大元素
        for (int i = 0; i < grid.size(); i++) {
            vector<int> row = grid[i];
            sort(row.begin(), row.end(), greater<int>());
            
            // 取前limits[i]个元素加入堆
            for (int j = 0; j < min(limits[i], (int)row.size()); j++) {
                pq.push(row[j]);
            }
        }
        
        // 取最大的k个元素
        long long sum = 0;
        for (int i = 0; i < k && !pq.empty(); i++) {
            sum += pq.top();
            pq.pop();
        }
        
        return sum;
    }
};

class Solution:
    def maxSum(self, grid: List[List[int]], limits: List[int], k: int) -> int:
        import heapq
        
        # 使用最大堆（Python中用负数模拟）
        max_heap = []
        
        # 对每行排序并取前limits[i]个最大元素
        for i in range(len(grid)):
            row = sorted(grid[i], reverse=True)
            
            # 取前limits[i]个元素加入堆
            for j in range(min(limits[i], len(row))):
                heapq.heappush(max_heap, -row[j])  # 负数模拟最大堆
        
        # 取最大的k个元素
        total_sum = 0
        for _ in range(min(k, len(max_heap))):
            total_sum += -heapq.heappop(max_heap)  # 取负数还原
        
        return total_sum

public class Solution {
    public long MaxSum(int[][] grid, int[] limits, int k) {
        var pq = new PriorityQueue<int, int>(Comparer<int>.Create((x, y) => y.CompareTo(x)));
        
        // 对每行排序并取前limits[i]个最大元素
        for (int i = 0; i < grid.Length; i++) {
            var row = new List<int>(grid[i]);
            row.Sort((x, y) => y.CompareTo(x));
            
            // 取前limits[i]个元素加入堆
            for (int j = 0; j < Math.Min(limits[i], row.Count); j++) {
                pq.Enqueue(row[j], row[j]);
            }
        }
        
        // 取最大的k个元素
        long sum = 0;
        for (int i = 0; i < k && pq.Count > 0; i++) {
            sum += pq.Dequeue();
        }
        
        return sum;
    }
}

var maxSum = function(grid, limits, k) {
    const maxHeap = new MaxPriorityQueue();
    
    // 对每行排序并取前limits[i]个最大元素
    for (let i = 0; i < grid.length; i++) {
        const row = [...grid[i]].sort((a, b) => b - a);
        
        // 取前limits[i]个元素加入堆
        for (let j = 0; j < Math.min(limits[i], row.length); j++) {
            maxHeap.enqueue(row[j]);
        }
    }
    
    // 取最大的k个元素
    let sum = 0;
    for (let i = 0; i < k && !maxHeap.isEmpty(); i++) {
        sum += maxHeap.dequeue().element;
    }
    
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n × m log m + S log S)其中 S 是所有可选元素的总数，排序每行需要 O(m log m)，建堆和取元素需要 O(S log S)
空间复杂度O(S)其中 S 是所有可选元素的总数，用于存储堆