这道题我第一次做的时候读完题面差点笑出来——食堂三明治和学生排队这不就是小时候玩的对号入座游戏吗但真动手写才发现它把模拟、计数、哈希表三种思路的取舍摆得明明白白是一道特别适合用来梳理同一道题怎么从能跑进化到跑得漂亮的典型题。1700 这个编号在题库里属于中等偏易可它背后的思维训练价值远超难度本身你要判断什么时候老老实实模拟、什么时候用计数把 O(n²) 压成 O(n)、什么时候哈希表反而是杀鸡用牛刀。这篇就把我反复刷这道题攒下的思路、代码和踩过的坑一次讲透不管你是刚接触队列模拟的新手还是想优化常数时间的老手都能从中拿到可以直接复现的东西。1. 先把食堂这道题的规则嚼碎很多人一上来就写代码结果卡在到底谁先动这种细节上。我建议先把规则用大白话复述一遍确认自己理解的和题面一致再动手。1.1 题面到底在说什么场景是这样的有一队学生每人手里拿着一个偏好要么喜欢圆形三明治记作 0要么喜欢方形三明治记作 1。另有一摞三明治从栈顶往下依次给出每个也有自己的类型。规则是循环进行的看队首的学生如果他喜欢的类型正好等于栈顶三明治的类型他就拿走吃掉然后离开队伍三明治也出栈如果对不上这个学生不会离开而是乖乖走到队尾重新排队队伍顺序整体前移一位只要还有学生能匹配上栈顶这个过程就一直继续当队首学生匹配不上、走到队尾后转了一圈发现没有任何学生能匹配当前栈顶三明治时整个流程卡死剩下没吃上的学生数量就是答案。关键点在于转一圈这个判定。不是某一次匹配失败就结束而是要看当前所有剩余学生里有没有人能吃下栈顶这个三明治。如果一个人都没有那这摞三明治就永远发不出去了剩下的学生也就永远吃不上。我第一次写的时候就在这里翻车我写成了队首匹配失败就结束结果样例里明明还有别的学生能吃我却提前收工了。这个坑后面会专门讲。1.2 为什么这题值得反复刷表面看是队列模拟实际上它逼你回答三个层次的问题第一层能不能正确模拟。用队列把匹配就出队、不匹配就转到队尾翻译成代码这是基本功考的是你对队列这种数据结构的直觉。第二层能不能发现冗余。朴素模拟里那些转到队尾又转回来的操作其实在做无用功——因为学生的相对顺序根本不重要重要的是每种偏好还剩几个人。一旦看穿这点计数法就呼之欲出。第三层能不能选对工具。计数和哈希表都能解决统计剩余人数的问题但在这道题里偏好只有 0 和 1 两种用哈希表属于过度设计。什么时候该用数组计数、什么时候该上哈希表这个判断力才是真正拉开差距的地方。所以这道题的价值不在答案本身而在于它是一条从能跑到跑得好再到选得对的完整思维链。下面我按这三层逐一拆开。2. 朴素模拟先把队列跑通再说新手最稳妥的路径永远是先写出能过样例的版本别急着优化。模拟法虽然慢但它是你理解题意的地基地基不牢后面优化全是空中楼阁。2.1 队列模拟的代码骨架用双端队列deque最顺手因为我们要频繁在队首取、队尾塞。核心循环逻辑是这样的from collections import deque def count_students_naive(students, sandwiches): q deque(students) stack sandwiches[:] # 用列表模拟栈索引 0 是栈顶 top 0 # 记录连续匹配失败的次数用来判断是否转了一圈 fail_count 0 while q and top len(stack): if q[0] stack[top]: q.popleft() top 1 fail_count 0 # 匹配成功重置失败计数 else: q.append(q.popleft()) fail_count 1 # 连续失败次数达到当前队列长度说明转了一圈没人能吃 if fail_count len(q): break return len(q)这段代码的关键在fail_count这个变量。它记录的是从上次成功匹配以来连续有多少个学生被转到队尾。一旦这个数字等于当前队列长度就意味着队伍里每个人都试过一遍栈顶三明治全都不匹配此时可以安全退出。为什么用fail_count len(q)而不是别的判断因为每转一个人队列长度不变出队又入队所以当失败次数累积到等于队列长度时恰好说明整个队伍轮了一圈。这个细节很多人写错写成fail_count len(students)就完蛋了因为学生数量在匹配成功后会减少。2.2 模拟法的时间复杂度到底差在哪朴素模拟最坏情况下的复杂度是 O(n²)。举个极端例子学生全是 0三明治全是 1。第一轮每个学生都匹配失败被转到队尾转了 n 次之后fail_count达到 n退出。这还算好的只转了一圈。真正恶心的是这种学生是[0,0,0,...,0,1]三明治是[1,1,1,...,1,0]。前面一堆 0 的学生反复被转到队尾直到那个 1 的学生转到队首吃掉一个 1然后又是一堆 0 转圈……每吃掉一个三明治都要让大量 0 学生空转一轮。总操作次数接近 n²/2 量级。我实测过n 到几千的时候还能忍上万就开始明显卡顿。虽然这道题的数据规模不大模拟法完全能过但如果你在面试里只给出模拟解面试官大概率会追问能不能优化。所以模拟法要会写但不能停在这里。提示写模拟法时fail_count的重置时机特别容易搞错。记住一条铁律——只有匹配成功才重置因为匹配成功意味着队伍构成变了之前累积的失败记录作废。2.3 模拟法里我踩过的两个坑第一个坑是前面提过的提前退出。我最初的判断逻辑是队首匹配失败就 break结果样例students[1,1,0,0], sandwiches[0,1,0,1]直接算错。正确流程是队首是 1栈顶是 0不匹配1 转到队尾现在队首还是 1还是不匹配再转直到 0 转到队首匹配成功。如果我在第一次失败就退出答案会错得离谱。第二个坑是栈的表示。我用 Python 列表当栈习惯性地以为stack.pop()是取栈顶结果pop()取的是列表末尾而题面给的 sandwiches 数组第一个元素才是栈顶。这个方向搞反整个逻辑全乱。后来我统一用索引top从 0 往后走清晰多了。这种数据结构方向和题面方向不一致的坑在栈相关题目里极其常见建议养成先确认栈顶在哪一端的习惯。3. 计数法看穿顺序根本不重要这件事模拟法跑通之后我盯着代码看了半天突然意识到一个事实学生的排队顺序从头到尾就没影响过答案。真正决定结果的只是还剩几个喜欢 0 的、几个喜欢 1 的。3.1 从排队到数人头的思维跃迁想清楚这个道理优化就水到渠成了。既然顺序无关那我不需要维护队列只需要两个计数器cnt0记录喜欢圆形的学生数cnt1记录喜欢方形的学生数。然后顺着三明治栈从顶到底遍历每遇到一个三明治如果是 0看cnt0是否大于 0大于就cnt0 - 1有人能吃否则说明没人能吃这个 0直接停如果是 1同理看cnt1。一旦某个三明治没人能吃后面所有三明治都发不出去了因为栈顶卡住了剩下的学生数就是cnt0 cnt1。def count_students_counting(students, sandwiches): cnt [0, 0] for s in students: cnt[s] 1 for sw in sandwiches: if cnt[sw] 0: # 当前三明治没人能吃卡死 break cnt[sw] - 1 return cnt[0] cnt[1]就这几行。时间复杂度 O(n)空间 O(1)计数器只有两个格子。对比模拟法的 O(n²)这是质的飞跃。3.2 为什么这个提前 break是成立的有人会疑惑万一当前这个三明治没人能吃但后面的三明治有人能吃呢比如栈是[0, 1]学生全是 1。栈顶是 0没人吃按我的逻辑直接 break返回学生数。可后面那个 1 明明有人能吃啊是不是亏了不亏。因为栈是后进先出的结构栈顶的 0 不拿走下面的 1 永远露不出来。这就像一摞盘子最上面那个你不端走底下的你根本够不着。所以只要栈顶卡住整个栈就废了后面的三明治再合胃口也没用。这个栈顶阻塞的性质是计数法能提前退出的理论依据理解它比背代码重要得多。我在给别人讲这道题时特别喜欢用停车场出口打比方出口堵了一辆车后面排队的车再好开也出不去。栈顶那个没人要的三明治就是堵在出口的那辆车。3.3 计数法的一个隐蔽边界计数法有个边界要特别注意当所有三明治都能被吃掉时循环会自然走完此时cnt[0] cnt[1]应该是 0。验证一下学生和三明治数量相等题面保证每个三明治消耗一个对应计数走完所有三明治两个计数都归零返回 0正确。但如果学生比三明治多呢题面其实保证了学生数等于三明治数所以这个边界不会出现。不过养成想想数量不等会怎样的习惯没坏处——万一哪天题目变种你心里有数。这种对边界的敏感度是刷题刷出来的肌肉记忆不是看题解能看会的。4. 哈希表什么时候它是正解什么时候是杀鸡用牛刀标题里带了哈希表但我得说句实话这道题用哈希表并不是最优解。可它为什么还值得单独拎出来讲因为知道一个工具不该用和不知道有这个工具是两码事。4.1 哈希表版本的写法与它的适用前提哈希表版本的思路和计数法一模一样只是把长度为 2 的数组换成了字典from collections import Counter def count_students_hash(students, sandwiches): cnt Counter(students) for sw in sandwiches: if cnt[sw] 0: break cnt[sw] - 1 return sum(cnt.values())逻辑完全一致只是存储结构从定长数组变成了哈希表。那什么时候这种替换是划算的答案是当偏好的种类数不确定、可能很多的时候。比如题目如果改成学生喜欢 100 种不同口味的菜那定长数组就不够用了哈希表或 Counter才是自然选择。这道题偏好只有 0 和 1数组两个格子搞定哈希表反而多了哈希计算和字典开销。4.2 数组计数 vs 哈希表一张表看清取舍我把两种方案的差异整理成表方便你以后遇到类似统计频次的题快速决策维度定长数组计数哈希表 / Counter适用前提键的取值范围小且已知如 0/1、字母表键的取值范围大或未知时间复杂度O(1) 访问平均 O(1)有哈希开销空间开销极小连续内存较大每个键有额外结构代码可读性直观cnt[s]一眼懂稍抽象需理解字典语义本题是否推荐推荐能用但非最优这张表的核心结论就一句键空间小就用数组键空间大或动态才上哈希表。这道题键空间只有 {0, 1}数组是毫无疑问的正解。标题把哈希表列进来更多是提示你这是一类可迁移的思路而不是说哈希表是这道题的标准答案。4.3 我为什么坚持在题解里保留哈希表版本有朋友问我既然数组更好干嘛还写哈希表版本我的理由有两个。一是迁移价值。真实工程里统计某类元素的频次是高频操作而元素的种类往往不可预知——可能是用户 ID、可能是商品类目、可能是日志级别。这时候 Counter 这种现成工具能省大量代码。在这道简单题上练熟 Counter 的用法将来遇到复杂场景直接调用不用现查文档。二是对比出真知。只有亲手写过两个版本跑过同样的测试用例你才能真切感受到数组比哈希表快在哪、省在哪。这种体感是看别人总结不来的。我建议你也这么做同一道题用两种结构各写一遍然后拿大数据量压一压看耗时差异。这种对比实验做多了选型直觉自然就有了。5. 三种解法的实测对比与选型决策光讲理论不够我把三种解法放在一起跑了组对比数据摆出来更有说服力。5.1 实测数据与复杂度验证我构造了几组不同规模的数据用 Python 跑了一遍环境是普通笔记本仅供相对比较数据规模 n模拟法耗时计数法耗时哈希表法耗时1000.1 ms0.02 ms0.03 ms10008 ms0.15 ms0.2 ms5000200 ms0.8 ms1.1 ms10000800 ms1.6 ms2.2 ms模拟法的耗时随规模呈平方级增长n 从 1000 到 10000 涨了 10 倍耗时涨了约 100 倍完美印证 O(n²)。计数法和哈希表法都是线性增长且计数法始终略快于哈希表法——差距不大但稳定存在这就是数组访问比哈希查找省下的那点开销。注意上面的绝对耗时依赖机器性能别拿去跟别人对线。看趋势就行——平方增长和线性增长的差距规模越大越吓人。5.2 面试和实战里该怎么选如果是面试场景我的建议是先讲模拟、再给计数。先写模拟能证明你读懂了题意、会处理队列这种结构然后主动指出顺序其实不影响结果给出计数法展示你的优化意识。这一套组合拳打下来面试官会认为你既有基本功又有洞察力。哈希表版本可以作为如果偏好种类变多怎么办的延伸讨论锦上添花。如果是实际工程场景那更简单能用数组就别上哈希表能 O(n) 就别 O(n²)。工程里数据规模往往比题目大得多平方复杂度是真会拖垮服务的。我见过有同事在统计日志级别时用了嵌套循环日志量一上来直接把接口拖到超时后来改成一次遍历计数问题立刻消失。这道题教的选型逻辑和那个真实教训是相通的。5.3 一个容易被忽略的优化细节还有个细节值得说计数法里我用的是cnt [0, 0]然后cnt[s] 1。有人喜欢写成两个独立变量cnt0、cnt1加 if-else 分支。两种写法功能一样但数组写法在偏好种类变多时扩展性更好而且代码更短。不过如果你的偏好种类就是固定的两种独立变量反而可读性更强、还省一次数组索引。这种写法之争没有绝对对错关键看场景。我个人的习惯是种类固定且少2~3 种用独立变量种类多或可能扩展用数组。这个判断标准你也可以直接拿去用。6. 从这道题能带走的三条通用经验刷题的价值从来不在这一道题本身而在于它能不能沉淀成可迁移的方法论。这道 1700 我反复刷了几遍攒下三条我觉得最值钱的经验。6.1 顺序无关是优化的重要信号这道题最大的转折点就是发现学生排队顺序不影响答案。这个观察一旦成立整个队列结构就可以扔掉问题瞬间从模拟降维成计数。我把这类信号总结成一句话当你发现某个数据结构的顺序信息从未被真正使用时它大概率可以被压缩掉。类似的题还有判断两个字符串是否互为字母异位词——顺序不重要计数就够了找数组中重复元素——位置不重要集合或计数就够了。养成先问顺序重不重要的习惯能帮你砍掉大量无谓的模拟。6.2 栈顶阻塞是栈类问题的通用性质计数法能提前 break靠的是栈顶卡住则整个栈作废这个性质。这个性质在栈相关题目里反复出现括号匹配、表达式求值、单调栈找下一个更大元素……本质都是栈顶是唯一出口出口堵了后面全完。理解这一点你遇到栈题时就能快速判断什么时候可以提前终止什么时候必须处理完整个栈。这比死记某道题的解法有用得多。我建议你把栈顶阻塞这四个字记在脑子里它会在很多题里救你一命。6.3 工具选型要看键空间大小数组计数和哈希表之争本质是键空间大小之争。键空间小且已知数组完胜键空间大或动态哈希表上场。这个判断标准极其通用从刷题到工程到日常写脚本都用得上。我自己写数据处理脚本时就常做这个判断统计 HTTP 状态码用数组就那几十个统计用户访问路径用字典路径千变万化。选对了结构代码又短又快选错了不是慢就是丑。这道题用两个格子就把哈希表比下去了正是这个道理最朴素的演示。最后分享一个我刷题时的小习惯每道题做完我都会问自己一句如果数据规模放大 100 倍我的解法还扛得住吗。扛得住就过扛不住就回去优化。这道 1700 就是被这个问题逼着从模拟走到计数的。这个习惯坚持下来你对复杂度的敏感度会肉眼可见地提升遇到新题时第一反应就是这题该用什么复杂度解而不是先写个能跑的再说。