Medium

题目描述

给你一个整数数组 banned 和两个整数 n 和 maxSum。你需要按照下述规则选择一些整数：

  • 所选整数必须在范围 [1, n] 内。
  • 每个整数最多只能选择一次。
  • 所选整数不能在数组 banned 中。
  • 所选整数的和不能超过 maxSum。

返回按照上述规则可以选择的整数的最大数量。

示例 1：

输入：banned = [1,6,5], n = 5, maxSum = 6
输出：2
解释：你可以选择整数 2 和 4。
2 和 4 都在范围 [1, 5] 内，都没有在 banned 中出现，它们的和是 6，没有超过 maxSum。

示例 2：

输入：banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
输出：0
解释：在遵循上述条件的情况下，你无法选择任何整数。

示例 3：

输入：banned = [11], n = 7, maxSum = 50
输出：7
解释：你可以选择整数 1, 2, 3, 4, 5, 6 和 7。
它们都在范围 [1, 7] 内，都没有在 banned 中出现，它们的和是 28，没有超过 maxSum。

约束条件：

  • 1 <= banned.length <= 10^4
  • 1 <= banned[i], n <= 10^4
  • 1 <= maxSum <= 10^9

解题思路

这道题可以用贪心算法来解决。核心思路是：为了选择最多的数字，我们应该优先选择较小的数字，因为这样可以在不超过 maxSum 的前提下选择更多的数字。

解题步骤：

  1. 预处理禁用数字：将 banned 数组转换为哈希集合，便于快速查找某个数字是否被禁用
  2. 贪心选择：从 1 开始遍历到 n，对于每个不在 banned 中的数字，如果加上它不会超过 maxSum，就选择它
  3. 累计计数：记录选择的数字个数和当前总和

这种贪心策略是正确的，因为如果我们选择了一个较大的数字而不选择较小的数字，我们总可以用较小的数字替换较大的数字来获得更好的结果（选择更多数字）。

时间复杂度主要取决于遍历 1 到 n 的过程，哈希集合的查找是 O(1) 的。空间复杂度主要用于存储禁用数字的哈希集合。

代码实现

class Solution {
public:
    int maxCount(vector<int>& banned, int n, int maxSum) {
        unordered_set<int> bannedSet(banned.begin(), banned.end());
        
        int count = 0;
        int sum = 0;
        
        for (int i = 1; i <= n; i++) {
            if (bannedSet.find(i) == bannedSet.end()) {
                if (sum + i <= maxSum) {
                    sum += i;
                    count++;
                } else {
                    break;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        banned_set = set(banned)
        
        count = 0
        current_sum = 0
        
        for i in range(1, n + 1):
            if i not in banned_set:
                if current_sum + i <= maxSum:
                    current_sum += i
                    count += 1
                else:
                    break
        
        return count

public class Solution {
    public int MaxCount(int[] banned, int n, int maxSum) {
        HashSet<int> bannedSet = new HashSet<int>(banned);
        
        int count = 0;
        int sum = 0;
        
        for (int i = 1; i <= n; i++) {
            if (!bannedSet.Contains(i)) {
                if (sum + i <= maxSum) {
                    sum += i;
                    count++;
                } else {
                    break;
                }
            }
        }
        
        return count;
    }
}

var maxCount = function(banned, n, maxSum) {
    const bannedSet = new Set(banned);
    
    let count = 0;
    let sum = 0;
    
    for (let i = 1; i <= n; i++) {
        if (!bannedSet.has(i)) {
            if (sum + i <= maxSum) {
                sum += i;
                count++;
            } else {
                break;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + m)其中 n 是范围上限，m 是 banned 数组长度。需要遍历 1 到 n，构建哈希集合需要 O(m)
空间复杂度O(m)存储 banned 数字的哈希集合，m 是 banned 数组长度

相关题目