题目描述
思路解析
一句话答案：LeetCode 2554 从一个范围内选择最多整数用贪心：要个数最多而非和最大，同份预算里小数塞得进的更多，就在 1 到 n 里从小往大依次选、跳过 banned 禁选数、和一超 maxSum 就停。时间 O(n+m)、空间 O(m)。
在 1 到 n 里挑数，这题求的是个数最多还是和最大
给一个禁选数组 banned、上界 n 和预算 maxSum，要在整数范围 [1, n] 里挑一些互不相同、又都不在 banned 里的数，让它们的和不超过 maxSum，问最多能挑出几个。注意要的是「个数最多」，不是「和最大」。题面 banned=[1,6,5]、n=5、maxSum=6 时答案是 2。
为什么挑数得从小的入手，冲着大数去反而选不多
同一份预算，一个大数就能把它花光。拿 maxSum=6 说，直接挑个 6，只换来 1 个数；换成 1 加 2 加 3，同样花掉 6，却装下了 3 个。目标是个数，就该让每个数尽量省预算，优先挑小的。另一处别踩的地方在判断禁选：banned 可能很长，若每碰到一个数都拿它从头扫一遍数组，扫 n 个数、每次找 m 个就是 O(n·m)；先把 banned 塞进哈希集合（查在不在只花常数时间），每次判断就压到 O(1)。
从小往大选，凭什么就是最优的
这里用的是贪心（每步只挑当下最划算的那个、选完不回头）：从最小的数起，能选就选。为什么一定最优，拿交换论证（把某个解里的一步换成另一步、看会不会更差）看：假设某个最优解挑了较大的数 x，而有个更小、又没被禁的数 y 空着没挑，那就把 x 换成 y，挑的个数没变，累计和却更小，省出来的预算说不定还能再多塞一个。既然总能把大数往小数调而不变差，从小到大挑就不吃亏。
一路扫过去，预算和禁选这两关谁先谁后
先把 banned 全倒进哈希集合。然后让 i 从 1 走到 n，每到一个数分两关看：第一关算预算，当前累计和 s 加上 i，一旦超过 maxSum 就停掉整个循环——从小往大扫，这个数都装不下，后面更大的数一个也塞不进，接着往后试纯属白费；没超再过第二关，查 i 在不在禁选集合里，不在就把它选下，个数加一、累计和加上 i。还有个分寸：和恰好等于 maxSum 也算数，判断用小于等于。
拿题面这组 banned、n=5、maxSum=6 扫一遍
禁选集合是 {1,5,6}，起手答案 0、累计和 0。先看 1，累计和加 1 得 1 没超 6，可 1 在集合里，跳过。轮到 2，累计和加 2 得 2 没超 6，2 不被禁，选下，答案 1、累计和 2。轮到 3，累计和加 3 得 5 没超 6，3 也不被禁，选下，答案 2、累计和 5。轮到 4，累计和加 4 得 9 超过了 6，停掉整个循环，返回 2。这趟挑中 2 和 3；题面举的是 2 和 4，个数同样是 2，贪心只是顺手挑了更省预算的一对。
和一超就整个停，别写成 continue 往后蹭
时间 O(n+m)：建集合 O(m)、从 1 扫到 n 是 O(n)，而且和一超就 break，往往扫不满 n 就收工；空间 O(m)，只多那个禁选集合。和超了那一步最容易写错：若写成 continue 接着往后看，从小往大扫后面只会更超，白扫一整段，只能 break 把循环整个停掉。取等号那关也别写严格小于，和正好压到 maxSum 时会漏掉一个。至于禁选值落在 [1, n] 外，比如 banned 有个 11 而 n 只到 7，它就相当于没禁，集合查不中、照常参与挑选。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这套:从最小的数开始,先看和会不会超,超了就停;没超且不被禁就选下。下面每一帧都在套它。
范围 [1, 9] · 从最小的数开始考虑：先把舞台摆好。上面是 1 到 9 这 9 个数,就是可挑的范围。我们的预算 maxSum 是 16。开局答案 ans 是 0,已选数字的累计和 s 也是 0。策略是从最小的 1 开始,一个一个往后看。
把 banned 装进禁选集合 · 收下 2：正式扫之前,先把 banned 里的数放进一个哈希集合,这样待会儿判断某个数能不能选,查一下就是常数时间。banned 第一个是 2,把它收进集合,数轴上的 2 就涂灰,表示这个位置禁选。
禁选集合 · 收下 3：banned 里第二个是 3,也收进集合,数轴上的 3 跟着涂灰。你看 2 和 3 挨在一块,待会儿扫到它们会连着被跳过。
禁选集合 · 收下 6：最后一个禁选数是 6,收进集合,数轴上的 6 涂灰。到这里禁选集合建好了,里面是 2、3、6 三个数。这三个位置无论如何都不能选,别的位置才有机会。
指针就位 · 从 i = 1 开始扫：禁选集合建好,灰色三个是 2、3、6。现在把指针 i 指到最左边的 1,准备从这里从小到大一路扫过去。每到一个数,先卡预算、再卡禁选。开扫。
看第 1 个数 · 预算够,再看禁选：轮到数字 1。先算预算:0 加 1 等于 1,没有超过 16,和这一关过了。接着查禁选集合,1 不在里面,可以选。
选中数字 1 · 答案加一：两关都过,把 1 选下,数轴上标绿。答案 ans 加一变成 1,累计和 s 加上 1 变成 1。这就是我们要的:多攒一个数,预算还没花完,继续往后。
看第 2 个数 · 预算够,再看禁选：轮到数字 2。先算预算:1 加 2 等于 3,没有超过 16,和这一关过了。接着查禁选集合,发现 2 正好在里面,是个禁选数。
数字 2 被禁 · 跳过：既然 2 在禁选集合里,就跳过它,答案 ans 和累计和 s 都保持不变,继续看下一个数。
看第 3 个数 · 预算够,再看禁选：轮到数字 3。先算预算:1 加 3 等于 4,没有超过 16,和这一关过了。接着查禁选集合,发现 3 正好在里面,是个禁选数。
数字 3 被禁 · 跳过：既然 3 在禁选集合里,就跳过它,答案 ans 和累计和 s 都保持不变,继续看下一个数。
看第 4 个数 · 预算够,再看禁选：轮到数字 4。先算预算:1 加 4 等于 5,没有超过 16,和这一关过了。接着查禁选集合,4 不在里面,可以选。
选中数字 4 · 答案加一：两关都过,把 4 选下,数轴上标绿。答案 ans 加一变成 2,累计和 s 加上 4 变成 5。这就是我们要的:多攒一个数,预算还没花完,继续往后。
看第 5 个数 · 预算够,再看禁选：轮到数字 5。先算预算:5 加 5 等于 10,没有超过 16,和这一关过了。接着查禁选集合,5 不在里面,可以选。
选中数字 5 · 答案加一：两关都过,把 5 选下,数轴上标绿。答案 ans 加一变成 3,累计和 s 加上 5 变成 10。这就是我们要的:多攒一个数,预算还没花完,继续往后。
看第 6 个数 · 预算够,再看禁选：轮到数字 6。先算预算:10 加 6 等于 16,没有超过 16,和这一关过了。接着查禁选集合,发现 6 正好在里面,是个禁选数。
数字 6 被禁 · 跳过：注意这一下:6 加上去和是 16,恰好不超预算,可它偏偏在禁选集合里,所以照样不能选。预算这关过了不代表能选,禁选这关也得过。跳过它,答案和累计和都不动。
看第 7 个数 · 先算预算：轮到数字 7。规矩是先算预算:当前累计和 10 再加上 7 等于 17,已经超过了 16。既然连和都装不下,而且后面的数只会更大,那就没有必要再看了。
和超上限 · 直接停止扫描：把 7 标红,循环就停在这里。这是贪心从小到大的好处:一旦某个数让和超了预算,再往后的数更大,一个都塞不下,直接收工,不用一个个试。到此答案已经定了,是 3。
停止之后 · 后面更大的数不再看：循环停在 7 之后,后面的 8 和 9 比 7 还大,加进来只会更超预算,所以一个都不用再看,直接把它们跟 7 一起放下。这正是从小到大贪心的妙处:一旦停下,后面的全都可以不管。
回放 · 选中 1、4、5 共 3 个,答案 3：回放一遍。绿色的是最终选中的数:1、4、5,一共 3 个,它们的和是 10,没有超过预算 16。中间 2、3 因为被禁跳过,6 虽然和不超但也被禁,7 让和超了预算触发停止。所以答案就是 3,和开头说的对上了。
边界想清:被禁的数从头跳、预算太小一个不选、禁选值落在范围外时等于没禁。
面试重点:目标是个数最多故从小贪心、交换论证证明最优、n 巨大时改前缀和加二分。
参考代码
from __future__ import annotationsfrom 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复杂度
- 时间：O(n + m)，m 是 banned 的长度。建哈希集合把 banned 全部塞进去是 O(m);再从 1 到 n 扫一遍,每个数只做常数次的加法和集合查询,是 O(n)。合起来 O(n + m),实际因为和一超就停,往往扫不到 n 就结束
- 空间：O(m)，额外空间只有那个装 banned 的哈希集合,里面最多 m 个元素;累计和、答案、循环变量都是常数个,不随 n 增长。所以空间是 O(m)
易错点
面试追问把动画讲成自己的话
追问这题的核心思路是什么?
追问为什么从小到大贪心一定最优?
追问如果 n 非常大,比如到十亿,这套还行吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
找出出现至少三次的最长特殊子字符串 I
LeetCode 2981 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题