已实现O(n)复杂度卡牌博弈算法，能否进一步优化提速？

问题描述 #

给定有序整数卡牌列表（例如[1,24,3,4,5]），两名玩家轮流取牌，玩家1先手。规则如下：

• 玩家抽到偶数卡牌时，剩余卡牌顺序反转，游戏继续。
• 所有卡牌取完后，得分高者获胜；平局则玩家1获胜。

现有解法 #

我用指针法实现了功能：

• 初始化左指针i = 0、右指针j = n-1（n为卡牌总数），用标记记录当前取牌方向。
• 遍历卡牌，按当前方向取对应端点的牌，累加到对应玩家得分。
• 若取到偶数，切换取牌方向（模拟剩余序列反转）。
• 遍历结束后比较得分，输出获胜者。

该解法可正常运行，但时间复杂度为O(n)，需要遍历整个列表。

提问 #

是否存在时间复杂度低于O(n)的更高效实现方式？

回答 #

结论先行：不存在时间复杂度低于O(n)的解法，你的指针法已经是当前问题的最优实现。

原因很简单：

1. 每张卡牌的归属（被玩家1还是玩家2取走）完全依赖于前面所有取牌操作的顺序，尤其是偶数卡牌触发的反转会直接改变后续取牌方向，每一步状态都和前一步强绑定，根本没法跳过任何一张卡牌直接推导最终结果。
2. 要算出最终得分，必须明确每一张牌的归属，这意味着至少要遍历所有卡牌一次，O(n)是时间复杂度的下限。

当然，你可以做一些小优化来减少循环次数，比如遇到连续的奇数卡牌时批量计算得分：

• 比如当前方向是从左取，接下来有3个连续奇数，那玩家1拿第1个，玩家2拿第2个，玩家1拿第3个，直接把这三个数的和按规则加到对应玩家得分里，不用逐个处理。
  但这种优化只是减少了循环的常数项，整体时间复杂度还是O(n)，并没有降低复杂度的阶数。

极端情况比如全是偶数的列表，每次取牌都要切换方向，这种情况下连批量处理的空间都没有，必须逐个处理每一张牌。

所以你的现有解法已经是最优的了，不用再纠结低于O(n)的实现——理论上就做不到。

内容的提问来源于stack exchange，提问作者user1691278