Medium

题目描述

给你两个长度为 n 的整数数组 value 和 limit。

初始时，所有元素都是非激活状态。你可以按任意顺序激活它们。

  • 要激活索引 i 处的非激活元素，当前激活元素的数量必须严格小于 limit[i]。
  • 当你激活索引 i 处的元素时，它会将 value[i] 加到总激活值中（即所有已进行激活操作的元素的 value[i] 之和）。
  • 每次激活后，如果当前激活元素的数量变为 x，那么所有满足 limit[j] <= x 的元素 j 都会永久变为非激活状态，即使它们已经是激活状态。

通过最优选择激活顺序，返回你能获得的最大总和。

示例 1：

输入：value = [3,5,8], limit = [2,1,3] 输出：16

示例 2：

输入：value = [4,2,6], limit = [1,1,1] 输出：6

示例 3：

输入：value = [4,1,5,2], limit = [3,3,2,3] 输出：12

提示：

  • 1 <= n == value.length == limit.length <= 10^5
  • 1 <= value[i] <= 10^5
  • 1 <= limit[i] <= n

解题思路

这道题的关键洞察是：相同 limit 值的元素应该分组处理，因为每组的决策是独立的。

核心思路：

  1. 分组策略：将所有元素按照 limit 值进行分组。对于每个 limit 组，我们需要选择其中价值最高的若干个元素。

  2. 贪心选择：对于 limit = j 的组，假设该组有 m 个元素，我们最多只能激活 min(j, m) 个元素（因为当激活数量达到 j 时，这些元素会失效）。为了最大化价值，应该选择该组中价值最高的 min(j, m) 个元素。

  3. 实现方法：

    • 使用哈希表按 limit 值分组
    • 对每组使用最小堆来高效地选出前 k 大的元素
    • 维护大小为 j 的最小堆，遍历该组所有元素：
      • 如果堆大小小于 j，直接加入
      • 如果堆大小等于 j，且当前元素大于堆顶，则替换堆顶

  4. 优化：使用最小堆的好处是可以在 O(n log k) 时间内找到前 k 大元素，空间复杂度为 O(k)。

这种方法的正确性基于：不同 limit 组之间的选择互不影响，每组内部采用贪心策略选择价值最大的元素。

代码实现

class Solution {
public:
    long long maxTotal(vector<int>& value, vector<int>& limit) {
        unordered_map<int, vector<int>> groups;
        
        // 按limit分组
        for (int i = 0; i < value.size(); i++) {
            groups[limit[i]].push_back(value[i]);
        }
        
        long long total = 0;
        
        // 处理每个组
        for (auto& [lim, vals] : groups) {
            priority_queue<int, vector<int>, greater<int>> minHeap; // 最小堆
            
            for (int val : vals) {
                if (minHeap.size() < lim) {
                    minHeap.push(val);
                } else if (val > minHeap.top()) {
                    minHeap.pop();
                    minHeap.push(val);
                }
            }
            
            // 累加该组的贡献
            while (!minHeap.empty()) {
                total += minHeap.top();
                minHeap.pop();
            }
        }
        
        return total;
    }
};

class Solution:
    def maxTotal(self, value: List[int], limit: List[int]) -> int:
        from collections import defaultdict
        import heapq
        
        groups = defaultdict(list)
        
        # 按limit分组
        for i in range(len(value)):
            groups[limit[i]].append(value[i])
        
        total = 0
        
        # 处理每个组
        for lim, vals in groups.items():
            min_heap = []  # 最小堆
            
            for val in vals:
                if len(min_heap) < lim:
                    heapq.heappush(min_heap, val)
                elif val > min_heap[0]:
                    heapq.heapreplace(min_heap, val)
            
            # 累加该组的贡献
            total += sum(min_heap)
        
        return total

public class Solution {
    public long MaxTotal(int[] value, int[] limit) {
        var groups = new Dictionary<int, List<int>>();
        
        // 按limit分组
        for (int i = 0; i < value.Length; i++) {
            if (!groups.ContainsKey(limit[i])) {
                groups[limit[i]] = new List<int>();
            }
            groups[limit[i]].Add(value[i]);
        }
        
        long total = 0;
        
        // 处理每个组
        foreach (var kvp in groups) {
            int lim = kvp.Key;
            var vals = kvp.Value;
            var minHeap = new PriorityQueue<int, int>();
            
            foreach (int val in vals) {
                if (minHeap.Count < lim) {
                    minHeap.Enqueue(val, val);
                } else if (val > minHeap.Peek()) {
                    minHeap.Dequeue();
                    minHeap.Enqueue(val, val);
                }
            }
            
            // 累加该组的贡献
            while (minHeap.Count > 0) {
                total += minHeap.Dequeue();
            }
        }
        
        return total;
    }
}

var maxTotal = function(value, limit) {
    const n = value.length;
    const memo = new Map();
    
    function dp(activeCount, inactiveSet) {
        const key = activeCount + ',' + Array.from(inactiveSet).sort().join(',');
        if (memo.has(key)) return memo.get(key);
        
        let maxVal = 0;
        
        for (let i = 0; i < n; i++) {
            if (inactiveSet.has(i) || activeCount >= limit[i]) continue;
            
            const newActiveCount = activeCount + 1;
            const newInactiveSet = new Set(inactiveSet);
            
            for (let j = 0; j < n; j++) {
                if (limit[j] <= newActiveCount) {
                    newInactiveSet.add(j);
                }
            }
            
            const remainingValue = dp(newActiveCount - newInactiveSet.size + inactiveSet.size, newInactiveSet);
            maxVal = Math.max(maxVal, value[i] + remainingValue);
        }
        
        memo.set(key, maxVal);
        return maxVal;
    }
    
    return dp(0, new Set());
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n log k)，其中 n 是数组长度，k 是各组的大小
空间复杂度O(n)，用于存储分组和堆