题目描述
思路解析动画文字版
记牢一句:学生在队里怎么转都不改各类人的总数,真正决定谁吃不上的是三明治栈的顺序。数清两类人、按栈顶往下发,发到某类没人要就卡住,剩几个就是答案。
先看队伍。从队首到队尾是 [方1, 方2, 方3, 圆4, 圆5, 方6],方表示爱吃方形、圆表示爱吃圆形,编号只是给每个人贴个名牌,方便等会看清谁转到了后面。队首是方1,他排第一个,等会第一轮先轮到他。
再看下面这行三明治栈的说明。从栈顶到栈底依次是方、圆、圆、圆、方、方,栈顶用方括号框出来的就是当前要发的那个。规则是栈顶先发,队首学生爱吃就拿走、栈顶往下走一个;不爱吃就回队尾。开始一轮轮发。
第 1 轮,先看队首的 方1,他爱吃方形。现在栈顶是方形。正好对上了,他爱吃的就是栈顶这个,下一帧他就能拿走离队。
方1 拿走了栈顶这个方形三明治,开开心心离开队伍。栈顶往下走一个,已经吃到饭的人变成 1 个。现在队首换成了 方2,连续放弃的计数也清零,重新开始数。
第 2 轮,先看队首的 方2,他爱吃方形。现在栈顶是圆形。对不上,他不爱吃圆形。按规矩,下一帧他得把三明治让出去、自己回到队尾,栈顶保持不动。
方2 不爱吃圆形,把它让出去,自己绕到队伍最后面,栈顶一点没变。现在连续放弃的人数到了 1,队伍长度是 5。还没转满一整圈,后面可能还有人爱吃,继续看新的队首。
第 3 轮,先看队首的 方3,他爱吃方形。现在栈顶是圆形。对不上,他不爱吃圆形。按规矩,下一帧他得把三明治让出去、自己回到队尾,栈顶保持不动。
方3 不爱吃圆形,把它让出去,自己绕到队伍最后面,栈顶一点没变。现在连续放弃的人数到了 2,队伍长度是 5。还没转满一整圈,后面可能还有人爱吃,继续看新的队首。
第 4 轮,先看队首的 圆4,他爱吃圆形。现在栈顶是圆形。正好对上了,他爱吃的就是栈顶这个,下一帧他就能拿走离队。
圆4 拿走了栈顶这个圆形三明治,开开心心离开队伍。栈顶往下走一个,已经吃到饭的人变成 2 个。现在队首换成了 圆5,连续放弃的计数也清零,重新开始数。
第 5 轮,先看队首的 圆5,他爱吃圆形。现在栈顶是圆形。正好对上了,他爱吃的就是栈顶这个,下一帧他就能拿走离队。
圆5 拿走了栈顶这个圆形三明治,开开心心离开队伍。栈顶往下走一个,已经吃到饭的人变成 3 个。现在队首换成了 方6,连续放弃的计数也清零,重新开始数。
第 6 轮,先看队首的 方6,他爱吃方形。现在栈顶是圆形。对不上,他不爱吃圆形。按规矩,下一帧他得把三明治让出去、自己回到队尾,栈顶保持不动。
方6 不爱吃圆形,把它让出去,自己绕到队伍最后面,栈顶一点没变。现在连续放弃的人数到了 1,队伍长度是 3。还没转满一整圈,后面可能还有人爱吃,继续看新的队首。
第 7 轮,先看队首的 方2,他爱吃方形。现在栈顶是圆形。对不上,他不爱吃圆形。按规矩,下一帧他得把三明治让出去、自己回到队尾,栈顶保持不动。
方2 不爱吃圆形,把它让出去,自己绕到队伍最后面,栈顶一点没变。现在连续放弃的人数到了 2,队伍长度是 3。还没转满一整圈,后面可能还有人爱吃,继续看新的队首。
第 8 轮,先看队首的 方3,他爱吃方形。现在栈顶是圆形。对不上,他不爱吃圆形。按规矩,下一帧他得把三明治让出去、自己回到队尾,栈顶保持不动。
方3 不爱吃圆形,把它让出去,自己绕到队伍最后面,栈顶一点没变。现在连续放弃的人数到了 3,队伍长度是 3。这两个数相等了,意味着这一圈里每个人都对栈顶的圆形摇了头,谁都不会去拿,再转下去也是一样,过程到此必须停下。
停下来时队里还剩 [方6, 方2, 方3] 这 3 个人,他们清一色都只爱吃方形,可栈顶偏偏是圆形,谁来当队首都换不动它。这 3 个人就是无法吃到午餐的学生,答案就是 3。
换个更省事的角度回看。开局数一下,爱吃圆形的有 2 个、爱吃方形的有 4 个。三明治栈从顶往下是方圆圆圆方方,顺着发:第一个方先被一个爱方的拿走,接着连发三个圆,正好把 2 个爱圆的发完后还多出一个圆没人要,这时就卡住了,队里剩下的全是爱方的,还有 3 个。和轮转模拟数出来的完全一致。
边界:喜好和栈顶完全错开则全员卡住、答案等于人数;完全对上则答案 0。判停看的是「栈顶没人要」,不是队列空没空。
面试重点:轮转不改各类人数所以可计数;判停是「爱吃栈顶的人为 0」非队列空;返回另一种人数用 cnt[v 异或 1]。
参考代码
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 TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def countStudents(self, students: List[int], sandwiches: List[int]) -> int: cnt = Counter(students) for v in sandwiches: if cnt[v] == 0: return cnt[v ^ 1] cnt[v] -= 1 return 0复杂度
- 时间：O(n)，参考代码先扫一遍 students 数清两类人,再顺着 sandwiches 从栈顶往下走,各是一趟线性遍历,每步常数操作,合起来是 O(n)。动画里那种真去轮转队伍的笨办法最坏要 O(n²),计数法把它压成了线性
- 空间：O(1)，按峰值算额外空间:只用了一个长度固定为 2 的计数器 cnt,不随 n 变大,所以是常数。不需要额外开队列或栈,题目给的两个数组是输入、不计入额外开销
易错点
面试追问把动画讲成自己的话
追问为什么可以不真的模拟轮转,直接计数?
追问停止的判定到底是什么?为什么不是队列空?
追问返回值为什么是 cnt[v 异或 1] 而不是 cnt[v]?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
简化路径
LeetCode 71 · 中等 · 沿着 栈套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题