深入解析：LeetCode 390 消除游戏

文章目录

• • 摘要
  • 描述
  • 题解答案
  • 题解代码分析
  • • 代码细节解释
  • 示例测试及结果
  • 时间复杂度
  • 空间复杂度
  • 总结

摘要

在算法题中，经常会遇到一些“模拟类”的题目：一开始我们会忍不住想直接照步骤一步步操作，但很快就会发现这种方式效率低得吓人。这道 LeetCode 390 消除游戏就是典型的例子。表面上是数组模拟，但实际上考的是 数学规律。

本文会先介绍题目，然后分析解法，最后带上完整的 Swift Demo 和测试。

描述

题目的规则是这样的：

1. 我们有一个从 1 到 n 的递增数组。
2. 第一步，从左往右删除第一个数，然后每隔一个数删除一个，直到结尾。
3. 第二步，从右往左，同样删除第一个（最右边的数），然后每隔一个数删除一个。
4. 不断重复这两个步骤，直到数组只剩下一个数。

题目让我们返回最后剩下的那个数。

举个例子：

• 输入：n = 9

  arr = [1,2,3,4,5,6,7,8,9]
  第一次从左往右 → [2,4,6,8]
  第二次从右往左 → [2,6]
  第三次从左往右 → [6]
  最后剩下的就是 6

• 输入：n = 1

  arr = [1]
  直接返回 1

题解答案

如果你尝试直接用数组去模拟这个过程，很快就会发现效率问题。因为 n 最大能到 10^9，数组模拟完全不现实。

更好的办法是：找规律，直接数学递推。

我们发现：

• 每一轮操作后，剩下的数依然是一个等差数列。

• 关键是维护三个变量：

  1. 当前的 头元素 head
  2. 当前的 步长 step（每轮会翻倍）
  3. 当前的 剩余元素个数 n

• 每次从左往右时，head 一定会更新；从右往左时，只有在元素个数是奇数时 head 才会更新。

最后，当 n 缩小到 1 时，head 就是答案。

题解代码分析

下面是 Swift 的实现：

import Foundation
class Solution {
func lastRemaining(_ n: Int) -> Int {
var leftToRight = true
var remaining = n
var step = 1
var head = 1
while remaining > 1 {
// 从左到右，head 一定会更新
// 从右到左，只有当剩余是奇数时 head 才会更新
if leftToRight || remaining % 2 == 1 {
head += step
}
remaining /= 2
step *= 2
leftToRight.toggle()
}
return head
}
}

代码细节解释

1. head：代表当前数组的第一个数字。初始是 1。

2. step：代表相邻数字的间隔，初始为 1。每一轮删除一半数字，step 就要翻倍。

3. remaining：剩余元素的个数，每一轮都除以 2。

4. leftToRight：布尔值，记录方向。每一轮切换一次。

5. head 更新条件：

   • 如果是从左往右，必然更新；
   • 如果是从右往左，只有 remaining 是奇数时才更新。

这样就避免了真实的数组操作，复杂度大幅度下降。

示例测试及结果

我们来跑几个例子：

let solution = Solution()
print(solution.lastRemaining(9))   // 输出: 6
print(solution.lastRemaining(1))   // 输出: 1
print(solution.lastRemaining(10))  // 输出: 8
print(solution.lastRemaining(24))  // 输出: 14

运行结果：

• 输入 9 → 输出 6
• 输入 1 → 输出 1
• 输入 10 → 输出 8
• 输入 24 → 输出 14

完全符合预期。

时间复杂度

每一轮都会把剩余的数字减半，所以循环次数大约是 log(n)。
因此时间复杂度是 O(log n)。

空间复杂度

我们只用了常数个变量 (head, step, remaining, leftToRight)，所以空间复杂度是 O(1)。

总结

这道题的精髓就是 不要真的去模拟数组操作，而是用数学规律来迭代推导。

• 每一轮剩下的数依然是等差数列；
• 我们只要跟踪 head 的变化，就能在 O(log n) 的时间里解出结果；
• 这种思路在处理大规模数据时非常有用，避免了不必要的存储和计算。

换句话说，这是一道“数学建模 + 算法优化”的典型题。学会这个技巧，类似的问题就能迎刃而解。