LeetCode 题解工作台
石子游戏 VI
Alice 和 Bob 轮流玩一个游戏，Alice 先手。 一堆石子里总共有 n 个石子，轮到某个玩家时，他可以 移出 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。 给你两个长度为 n 的整数数组 aliceValues 和 b…
6
题型
5
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
选取石头的最优化的策略是，让自己得分最高，同时让对手失分最多。因此，我们创建一个数组 ，其中 $vals[i] = (aliceValues[i] + bobValues[i], i)$，表示第 个石头的总价值和编号。然后我们对 按照总价值降序排序。 然后我们按照 的顺序，让 Alice 和 Bob 交替选取石头。Alice 选取 中的偶数位置的石头，Bob 选取 中的奇数位置的石头。最…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
Alice 和 Bob 轮流玩一个游戏，Alice 先手。
一堆石子里总共有 n 个石子，轮到某个玩家时，他可以 移出 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。
给你两个长度为 n 的整数数组 aliceValues 和 bobValues 。aliceValues[i] 和 bobValues[i] 分别表示 Alice 和 Bob 认为第 i 个石子的价值。
所有石子都被取完后，得分较高的人为胜者。如果两个玩家得分相同，那么为平局。两位玩家都会采用 最优策略 进行游戏。
请你推断游戏的结果，用如下的方式表示：
- 如果 Alice 赢，返回
1。 - 如果 Bob 赢，返回
-1。 - 如果游戏平局，返回
0。
示例 1：
输入：aliceValues = [1,3], bobValues = [2,1] 输出：1 解释： 如果 Alice 拿石子 1 （下标从 0开始），那么 Alice 可以得到 3 分。 Bob 只能选择石子 0 ，得到 2 分。 Alice 获胜。
示例 2：
输入：aliceValues = [1,2], bobValues = [3,1] 输出：0 解释： Alice 拿石子 0 ， Bob 拿石子 1 ，他们得分都为 1 分。 打平。
示例 3：
输入：aliceValues = [2,4,3], bobValues = [1,6,7] 输出：-1 解释： 不管 Alice 怎么操作，Bob 都可以得到比 Alice 更高的得分。 比方说，Alice 拿石子 1 ，Bob 拿石子 2 ， Alice 拿石子 0 ，Alice 会得到 6 分而 Bob 得分为 7 分。 Bob 会获胜。
提示：
n == aliceValues.length == bobValues.length1 <= n <= 1051 <= aliceValues[i], bobValues[i] <= 100
解题思路
方法一：贪心 + 排序
选取石头的最优化的策略是，让自己得分最高，同时让对手失分最多。因此，我们创建一个数组 ，其中 ，表示第 个石头的总价值和编号。然后我们对 按照总价值降序排序。
然后我们按照 的顺序，让 Alice 和 Bob 交替选取石头。Alice 选取 中的偶数位置的石头，Bob 选取 中的奇数位置的石头。最后比较 Alice 和 Bob 的得分，返回对应的结果。
时间复杂度 ，空间复杂度 ，其中 为数组 aliceValues 和 bobValues 的长度。
class Solution:
def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:
vals = [(a + b, i) for i, (a, b) in enumerate(zip(aliceValues, bobValues))]
vals.sort(reverse=True)
a = sum(aliceValues[i] for _, i in vals[::2])
b = sum(bobValues[i] for _, i in vals[1::2])
if a > b:
return 1
if a < b:
return -1
return 0
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n log n) due to sorting the stones by combined value. Space complexity is O(n) for storing the combined values and scores. The greedy selection avoids more complex DP solutions, exploiting the invariant that the highest combined value stone is always the optimal next choice. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask why sorting by combined value works instead of sorting by individual player values.
- question_mark
Probe understanding of why each turn affects both players' potential scores.
- question_mark
Check if the candidate considers edge cases like draws or stones with equal combined value.
常见陷阱
外企场景- error
Sorting by only Alice's or Bob's value can mislead the greedy choice.
- error
Failing to alternate turns correctly can invert expected score advantage.
- error
Ignoring the opponent's potential points from each stone leads to wrong winner calculation.
进阶变体
外企场景- arrow_right_alt
Game with three players, requiring tracking cumulative impact across all three scores.
- arrow_right_alt
Stones with negative values, adding risk management to greedy selection.
- arrow_right_alt
Allowing removal of multiple stones per turn, changing the invariant for optimal selection.