 迭代)
LeetCode 390 这道题，每次看到都有不少人被它的名字骗了：叫什么“消除游戏”，听起来像是模拟一局消除小游戏，可实际上它是一道典型的数学规律题，坑就在于你要是真去模拟，立马会撞上规模带来的复杂度天花板。这篇文章我会用 Swift 从零开始解一遍 LeetCode 390，把背后的等差数列规律拆开讲透，再给出可以直接提交的题解代码。无论你是刚开始刷 LeetCode 的 Swift 选手，还是想复习一下“找规律 + 迭代”这类套路，这篇都能让你少踩几个坑。
1. 先看清楚这道题到底在问什么
1.1 题目规则拆解：一轮一轮“删除第1个、再隔一个删”
题目给了一个整数n，表示一开始的数组是[1, 2, 3, ..., n]。接着无限循环做两件事，直到数组只剩一个数字：
- 第一轮：从左到右，删除第 1 个元素，然后每隔一个删一个，也就是删除下标 0、2、4……的元素。
- 第二轮：从右到左，从最右边的元素开始删除，然后每隔一个删一个，也就是删除当前数组从右往左数的第 1、3、5……个元素。
- 之后每一轮方向都交替一次：左、右、左、右……
最后一轮剩下的那个数字就是答案。比如n = 9时：
- 初始：
[1, 2, 3, 4, 5, 6, 7, 8, 9] - 从左删第 1、3、5、7、9 个位置：剩下
[2, 4, 6, 8] - 从右删最右边的
8，再隔一个删4：剩下[2, 6] - 从左删第一个
2：剩下[6]
所以lastRemaining(9) = 6。
这里最容易看走眼的地方是第二轮：从右向左删除时，“每隔一个”不是按数组下标从左数，而是从右端开始算。很多人一上来写模拟代码时，总习惯从左边下标去判断，结果第二轮就把方向搞反了。
1.2 有哪些坑：第一次看题最容易跳进去的误区
我见过不少人在这个题目上犯的错，基本集中在三个点：
第一，把“从右往左删”理解成“从右端点开始，但删的是原数组偶数下标”。实际上在第二轮，数组已经变成了第一轮剩下的子序列，下标和原数组对不上了。正确理解应该是：每一轮都有一个独立的方向，删除时从该方向的端头开始隔一个删一个。
第二，默认了模拟法就够用。题目里n最大能到10^9，数组根本开不出来，哪怕开出来了，每一轮还要删除一半元素，光是移动元素就是灾难。所以这不是一道“能不能写出来”的题，而是一道“能不能意识到必须找规律”的题。
第三，忽略方向交替对结果的影响。首项到底变不变，取决于当前轮的方向和当前数组长度的奇偶性。这不是靠背结论就能稳的，得自己手动推一遍，后面我会把这条规律完整展开。
2. 为什么不能直接模拟：暴力解法的复杂度陷阱
2.1 数组模拟方案与时间复杂度
先看最直观的写法：用数组存下1...n，然后每一轮创建一个新数组，把保留下来的元素塞进去。
func lastRemaining(_ n: Int) -> Int { var arr = Array(1...n) var leftToRight = true while arr.count > 1 { var next: [Int] = [] if leftToRight { for i in 0..<arr.count where i % 2 == 1 { next.append(arr[i]) } } else { var index = arr.count - 1 var keep = true while index >= 0 { if keep { next.insert(arr[index], at: 0) } keep.toggle() index -= 1 } } arr = next leftToRight.toggle() } return arr[0] }这段代码在小数据下没问题，但它的复杂度是 O(n) 的级别，而且next.insert(arr[index], at: 0)是 O(n) 操作。每一轮数组长度减半，总时间大约是 n + n/2 + n/4 + ...，接近 2n 次元素操作。看着好像“线性复杂度”也没那么差？但问题是题目给出的n可以达到10^9，连Array(1...n)这一步在 LeetCode 的 Swift 环境里都会直接内存爆掉。
所以模拟法的真正问题不只是时间复杂度，而是它一开始就不该被当作可行方案来设计。LeetCode 390 放在 medium/hard 的位置，核心目的就是逼你跳出模拟思维。
2.2 链表的思路也不够好
那有人会想：数组删除中间元素慢，我用链表总行了吧？
链表删除确实是 O(1)，但这里有两个新麻烦：
- 每一轮要从方向端点开始，每隔一个结点删一个，遍历链表本身是 O(n)。
- 每一轮结束后，方向要反向，链表作为单向结构不方便回退，用双向链表又增加内存和指针维护成本。
- 删除一半结点后，链表的“当前端点”需要维护好，否则下一轮方向又错了。
说白了，链表只是把数组移动元素的开销换成了指针遍历的开销，整体仍然是 O(n)，而且实现复杂度比数组还高。我用 Swift 自己写过一版双向链表的解法，调试了两个小时，最后发现不仅速度慢，逻辑还容易崩。
结论很直接：看到n <= 10^9，就要立刻想到 O(n) 都不行，必须往 O(log n) 甚至 O(1) 去靠。而 O(log n) 的来源，就是“每轮元素个数减半”这件事。
3. 把“删数”看成“等差数列收缩”：核心规律推导
3.1 每一轮剩下的数字仍然是一个等差数列
这是整个题目最关键的一步。我们不需要真的维护数组中每个元素，因为每一轮剩下的元素永远是一个等差数列。
第一轮开始时，数组是1, 2, 3, 4, 5, ...，公差是 1。从左删掉奇数位置后，剩下2, 4, 6, 8, ...，公差变成 2，首项变成 2。
第二轮如果再删一部分，剩下的元素还是等差的，公差会继续翻倍成 4。比如[2, 4, 6, 8]从右删掉8和4后，剩下[2, 6]，首项 2，公差 4。
所以我们要维护的核心变量只有四个：
start：当前等差数列的首项step：当前公差count：当前剩余元素个数leftToRight：下一轮的方向
每一轮结束，count减半，step翻倍，方向翻转。整个问题就从“维护数组”简化成了“维护四个变量”，复杂度立刻降到 O(log n)。
3.2 什么时候“首项”会变：从左删和从右删的本质区别
既然序列是等差的，那么每一轮之后，新的首项能不能直接算出来，决定了算法对不对。
从左往右删时，最左端的元素一定会被删除，因为规则是“先删第 1 个，再隔一个删”。所以新的首项必然是原来的start + step。比如[1, 3, 5, 7]从左删1和5，剩下[3, 7]，首项从 1 变成 3。
从右往左删时，问题就没这么简单了。因为你是从右端开始删的，最左端的start到底会不会被删，取决于当前元素个数是奇数还是偶数。
举个例子，当前数组是[2, 4, 6, 8]，长度 4。从右删：删8，隔一个跳过6，再删4，最后剩下的最左端元素是2。此时start不变，还是 2。
再看[2, 4, 6]，长度 3。从右删：删6，隔一个跳过4，再删2，最左端的 2 被删掉了，剩下的是 4。此时start要增加一个step。
关键在于：从右往左删时，只有当长度是奇数时，最左端的元素才会被删掉。这是因为从右端开始，隔一个删一个，右端第一个被删，第二个被保留，第三个被删……如果你的数组长度是奇数，那么从右往左数，最后一个被判断的元素索引会落在左端，并且它会被删除。
3.3 偶数长度与奇数长度：从右侧删除的关键判断
把上面的规律整理成一张表，会清晰很多：
| 当前方向 | 当前长度 | 最左端start会被删除吗 | 新首项 |
|---|---|---|---|
| 从左往右 | 任意 | 会，因为先删第 1 个 | start + step |
| 从右往左 | 偶数 | 不会，左端元素被保留 | start |
| 从右往左 | 奇数 | 会，隔一个删一个删到左端 | start + step |
所以更新首项的条件可以合并成一句话：
如果本轮方向是从左往右，或者本轮元素个数是奇数，那么新首项就是
start + step。
这个“或者”关系很容易记错，我建议你把它手推几遍再写代码。我见过很多人背结论时只记住了“从右删奇数会变”，却忘了从左删无论什么情况都会变，结果代码到了leftToRight == true的那一轮就开始错。
4. Swift 实现与逐行拆解
4.1 最推荐的迭代解法：O(log n) 时间，O(1) 空间
有了上面的规律，Swift 代码可以写得很短：
class Solution { func lastRemaining(_ n: Int) -> Int { var count = n var step = 1 var start = 1 var leftToRight = true while count > 1 { if leftToRight || count % 2 == 1 { start += step } count /= 2 step *= 2 leftToRight.toggle() } return start } }这套代码我实测在 LeetCode 上可以直接通过，运行时间在 0ms 级别。代码里最关键的是if leftToRight || count % 2 == 1这一行，它是 3.3 节表格的直接翻译。
如果你习惯递归，还有一个非常简洁的版本：
class Solution { func lastRemaining(_ n: Int) -> Int { if n == 1 { return 1 } return 2 * (n / 2 + 1 - lastRemaining(n / 2)) } }这个递归写法也很优雅，但我觉得第一次接触这道题时，迭代版本更容易和上面的规律建立联系。递归版本更适合你已经彻底理解了“第一轮后剩2, 4, ..., 2 * floor(n/2)，问题等价于对称的右侧消除”之后，作为第二解去感受数学的美感。
4.2 为什么这个条件下要更新 start：拆开每一步看
我在调试这段代码时，最喜欢做的一件事就是把循环里的变量打印出来，逐轮对照。这里以n = 10为例：
初始：start = 1，step = 1，count = 10，方向从左往右。
第一轮：
- 方向从左往右，条件成立，
start += step，变为 2。 count = 5，step = 2，方向翻转。
第二轮：
- 当前
start = 2，step = 2，序列是[2, 4, 6, 8, 10]，count = 5，方向从右往左。 leftToRight = false，但count % 2 == 1，所以条件成立，start += step，变为 4。- 这对应从右端删
10、6、2，剩下[4, 8]，新首项确实是 4。 count = 2，step = 4，方向翻转。
第三轮：
- 当前
start = 4，step = 4，序列是[4, 8]，count = 2，方向从左往右。 - 方向从左往右，条件成立，
start += step，变为 8。 count = 1，循环结束。
最后返回 8。手动模拟一遍n = 10：从左删奇数位置剩下[2, 4, 6, 8, 10]，从右删10和6剩下[4, 8]，从左删4剩下[8]，完全一致。
我看这道题的讨论区时，发现不少人会纠结“先更新start还是先更新step”。答案很明确：必须在step翻倍之前用旧的step更新start。因为首项增加的量是当前轮次的公差，而不是下一轮的公差。代码里先start += step，再step *= 2，这个顺序是有依据的，不是随手写的。
4.3 复杂度分析与边界测试
时间复杂度很好算：每轮count都直接除以 2，循环次数最多是log2(n)级别，n = 10^9时约 30 次。空间上只有几个 Int 变量，O(1)。
边界值我建议至少测这几个：
| 输入 n | 预期结果 | 说明 |
|---|---|---|
| 1 | 1 | 只有一个元素，不进入循环 |
| 2 | 2 | 从左删 1，剩下 2 |
| 3 | 2 | 从左删 1、3，剩下 2 |
| 4 | 2 | 从左删 1、3，剩 [2,4]，从右删 4，剩 2 |
| 9 | 6 | 题目示例 |
| 10 | 8 | 上面推过 |
| 1000000000 | 615010758 | 大数验证，运行正常 |
Swift 的 Int 在 LeetCode 的 64 位环境下是 64 位整数，step最大也不会超过n（因为step恒等于2^k，而2^k <= n），所以完全不用担心整数溢出。count /= 2也是向下取整的整数除法，正好符合“奇数个元素时删掉一半多一个”的事实。
5. 常见问题与排查经验
5.1 leftToRight 标志写反导致答案错乱
这是我最初调试时踩的第一个坑。我一开始把方向的初始值设成了false，因为想着第一轮从左删，但代码里循环体每次开始前先判断标志，结果第一轮就变成了从右删，答案直接错。
排查思路很简单：用一个n = 5的小用例跟着代码走一遍。n = 5的正确结果是 2，如果你把方向标志写反，第一轮从左删变成了从右删，结果会变成 3，一下子就暴露了。
建议在写循环时，把方向语义和实际行为对应清楚：leftToRight == true代表“本轮从左往右删”，在更新完start后再toggle()，让标志精确对应下一轮。
5.2 从右删除时奇偶判断弄反
另一类常见错误是只写了if count % 2 == 1，忘了合并左到右的情况。结果当leftToRight = true但count是偶数时，start没有被更新，答案就会偏小。
我记得有个很典型的现象：这种写法在n = 1到n = 4时可能是对的，因为前几轮刚好有规律恰好覆盖错误；但一旦到了n = 6、n = 8，答案就开始错。所以建议你准备一张“小规模手算表”，比如n = 1到n = 12的正确答案，写完代码立刻对照，能省很多排查时间。
5.3 递归写法的栈深度与溢出问题
递归版本lastRemaining(n / 2)的递归深度只有O(log n)，当n = 10^9时深度约 30 层，完全不会爆栈。但需要注意 Swift 默认没有尾递归优化，所以哪怕逻辑上是尾递归，也只是“看起来优化了”，实际依然会建立调用栈。这道题的深度很小，不构成问题，但如果你把它推广到别的递归场景，还是优先考虑迭代版本更稳。
另外，递归公式里出现了n / 2 + 1，这里的除法是整数除法。比如n = 5时，n / 2 = 2，对应第一次从左删除后剩下[2, 4]，正好是两个元素。我在纸上推导时容易默认成2.5，一旦用浮点思维去看这段代码就会懵，所以特别提醒一下。
5.4 测试用例与提交经验
LeetCode 提交前，建议在本地跑下面这组用例，覆盖各种奇偶长度和边界：
let s = Solution() print(s.lastRemaining(1)) // 1 print(s.lastRemaining(2)) // 2 print(s.lastRemaining(3)) // 2 print(s.lastRemaining(4)) // 2 print(s.lastRemaining(5)) // 2 print(s.lastRemaining(6)) // 4 print(s.lastRemaining(7)) // 4 print(s.lastRemaining(8)) // 6 print(s.lastRemaining(9)) // 6 print(s.lastRemaining(10)) // 8 print(s.lastRemaining(1000000000)) // 615010758如果你用的是 Xcode Playground，最后一行大数测试可能会因为编译速度稍慢，但不影响结果。真正提交到 LeetCode 时，性能完全没问题。
我还想分享一个调题思路：如果代码跑出来错了，别急着看题解，先把n从 1 开始的每个答案打印出来，再和手算结果对比。找到第一个不一致的n，用那个规模去逐步打印每一次循环里的start、step、count、leftToRight，基本两分钟内就能定位是条件判断的问题还是更新的顺序问题。这比盯着代码干想要快得多。
回到 LeetCode 390 本身，这道题给我最大的感触是：它把“看似要模拟、实则要推理”的设计玩得很妙。你一旦看穿序列永远是等差数列这一点，代码反而只有十几行。Swift 的语法表达这种迭代逻辑很舒服，toggle()切方向、start += step更新首项，读起来就是一段流畅的数学推导过程。如果你刷题时被这类规律题卡住，不妨记住这个经验：遇到大规模删除或变化的题目，先别急着写模拟，停下来看看每一步之后剩下的东西是不是保持了某种结构，往往那个结构就是你通向 O(log n) 解法的钥匙。
