从一个范围内选择最多整数 I 图解题解

这道题到底在问什么

输入

banned=[1,6,5], n=5, maxSum=6

输出

2 (选 2 和 4,和是 6)

输入

banned=[11], n=7, maxSum=50

输出

7 (1 到 7 全选,和 28 没超)

先想最直接的笨办法

先把舞台摆好。上面是 1 到 9 这 9 个数,就是可挑的范围。我们的预算 maxSum 是 16。开局答案 ans 是 0,已选数字的累计和 s 也是 0。策略是从最小的 1 开始,一个一个往后看。（动画第 4 步）

最优解：一步一步想明白

1. 3记牢这套:从最小的数开始,先看和会不会超,超了就停;没超且不被禁就选下。下面每一帧都在套它。
2. 4先把舞台摆好。上面是 1 到 9 这 9 个数,就是可挑的范围。我们的预算 maxSum 是 16。开局答案 ans 是 0,已选数字的累计和 s 也是 0。策略是从最小的 1 开始,一个一个往后看。
3. 5正式扫之前,先把 banned 里的数放进一个哈希集合,这样待会儿判断某个数能不能选,查一下就是常数时间。banned 第一个是 2,把它收进集合,数轴上的 2 就涂灰,表示这个位置禁选。
4. 6banned 里第二个是 3,也收进集合,数轴上的 3 跟着涂灰。你看 2 和 3 挨在一块,待会儿扫到它们会连着被跳过。
5. 7最后一个禁选数是 6,收进集合,数轴上的 6 涂灰。到这里禁选集合建好了,里面是 2、3、6 三个数。这三个位置无论如何都不能选,别的位置才有机会。
6. 8禁选集合建好,灰色三个是 2、3、6。现在把指针 i 指到最左边的 1,准备从这里从小到大一路扫过去。每到一个数,先卡预算、再卡禁选。开扫。
7. 9轮到数字 1。先算预算:0 加 1 等于 1,没有超过 16,和这一关过了。接着查禁选集合,1 不在里面,可以选。
8. 10两关都过,把 1 选下,数轴上标绿。答案 ans 加一变成 1,累计和 s 加上 1 变成 1。这就是我们要的:多攒一个数,预算还没花完,继续往后。
9. 11轮到数字 2。先算预算:1 加 2 等于 3,没有超过 16,和这一关过了。接着查禁选集合,发现 2 正好在里面,是个禁选数。
10. 12既然 2 在禁选集合里,就跳过它,答案 ans 和累计和 s 都保持不变,继续看下一个数。
11. 13轮到数字 3。先算预算:1 加 3 等于 4,没有超过 16,和这一关过了。接着查禁选集合,发现 3 正好在里面,是个禁选数。
12. 14既然 3 在禁选集合里,就跳过它,答案 ans 和累计和 s 都保持不变,继续看下一个数。
13. 15轮到数字 4。先算预算:1 加 4 等于 5,没有超过 16,和这一关过了。接着查禁选集合,4 不在里面,可以选。
14. 16两关都过,把 4 选下,数轴上标绿。答案 ans 加一变成 2,累计和 s 加上 4 变成 5。这就是我们要的:多攒一个数,预算还没花完,继续往后。
15. 17轮到数字 5。先算预算:5 加 5 等于 10,没有超过 16,和这一关过了。接着查禁选集合,5 不在里面,可以选。
16. 18两关都过,把 5 选下,数轴上标绿。答案 ans 加一变成 3,累计和 s 加上 5 变成 10。这就是我们要的:多攒一个数,预算还没花完,继续往后。
17. 19轮到数字 6。先算预算:10 加 6 等于 16,没有超过 16,和这一关过了。接着查禁选集合,发现 6 正好在里面,是个禁选数。
18. 20注意这一下:6 加上去和是 16,恰好不超预算,可它偏偏在禁选集合里,所以照样不能选。预算这关过了不代表能选,禁选这关也得过。跳过它,答案和累计和都不动。
19. 21轮到数字 7。规矩是先算预算:当前累计和 10 再加上 7 等于 17,已经超过了 16。既然连和都装不下,而且后面的数只会更大,那就没有必要再看了。
20. 22把 7 标红,循环就停在这里。这是贪心从小到大的好处:一旦某个数让和超了预算,再往后的数更大,一个都塞不下,直接收工,不用一个个试。到此答案已经定了,是 3。
21. 23循环停在 7 之后,后面的 8 和 9 比 7 还大,加进来只会更超预算,所以一个都不用再看,直接把它们跟 7 一起放下。这正是从小到大贪心的妙处:一旦停下,后面的全都可以不管。
22. 24回放一遍。绿色的是最终选中的数:1、4、5,一共 3 个,它们的和是 10,没有超过预算 16。中间 2、3 因为被禁跳过,6 虽然和不超但也被禁,7 让和超了预算触发停止。所以答案就是 3,和开头说的对上了。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        ans = s = 0
        ban = set(banned)
        for i in range(1, n + 1):
            if s + i > maxSum:
                break
            if i not in ban:
                ans += 1
                s += i
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maxCount(vector<int>& banned, int n, int maxSum) {
        unordered_set<int> ban(banned.begin(), banned.end());
        int ans = 0, s = 0;
        for (int i = 1; i <= n && s + i <= maxSum; ++i) {
            if (!ban.count(i)) {
                ++ans;
                s += i;
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int maxCount(int[] banned, int n, int maxSum) {
        Set<Integer> ban = new HashSet<>(banned.length);
        for (int x : banned) {
            ban.add(x);
        }
        int ans = 0, s = 0;
        for (int i = 1; i <= n && s + i <= maxSum; ++i) {
            if (!ban.contains(i)) {
                ++ans;
                s += i;
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问