题目描述
思路解析动画文字版
记牢这套:从最小的数开始,先看和会不会超,超了就停;没超且不被禁就选下。下面每一帧都在套它。
范围 [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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题