Medium

题目描述

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.length
  • 1 <= n <= 10^5
  • 1 <= aliceValues[i], bobValues[i] <= 100

解题思路

这道题的关键洞察是：当一个玩家选择一颗石子时，不仅获得了对应的分数，还阻止了对手获得该石子的分数。

因此，选择第 i 颗石子的实际价值应该是 aliceValues[i] + bobValues[i]，因为：

  • Alice 选择石子 i 时，Alice 获得 aliceValues[i] 分，同时让 Bob 失去 bobValues[i] 分
  • Bob 选择石子 i 时，Bob 获得 bobValues[i] 分，同时让 Alice 失去 aliceValues[i] 分

解题步骤：

  1. 计算每颗石子的总价值 aliceValues[i] + bobValues[i]
  2. 按照总价值从高到低排序
  3. Alice 和 Bob 轮流选择价值最高的石子（贪心策略）
  4. 计算最终得分差，判断胜负

贪心策略的正确性： 由于双方都会优先选择能让自己相对收益最大的石子，而 aliceValues[i] + bobValues[i] 正好代表了选择第 i 颗石子对选择者的相对优势，所以按此排序的贪心选择是最优的。

时间复杂度主要来自排序操作，空间复杂度用于存储石子索引和对应的总价值。

代码实现

class Solution {
public:
    int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) {
        int n = aliceValues.size();
        vector<pair<int, int>> stones; // {total_value, index}
        
        for (int i = 0; i < n; i++) {
            stones.push_back({aliceValues[i] + bobValues[i], i});
        }
        
        sort(stones.rbegin(), stones.rend()); // 按总价值降序排序
        
        int aliceScore = 0, bobScore = 0;
        for (int i = 0; i < n; i++) {
            int idx = stones[i].second;
            if (i % 2 == 0) { // Alice 的回合
                aliceScore += aliceValues[idx];
            } else { // Bob 的回合
                bobScore += bobValues[idx];
            }
        }
        
        if (aliceScore > bobScore) return 1;
        else if (aliceScore < bobScore) return -1;
        else return 0;
    }
};

class Solution:
    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:
        n = len(aliceValues)
        stones = []
        
        for i in range(n):
            stones.append((aliceValues[i] + bobValues[i], i))
        
        stones.sort(reverse=True)  # 按总价值降序排序
        
        alice_score = 0
        bob_score = 0
        
        for i in range(n):
            _, idx = stones[i]
            if i % 2 == 0:  # Alice 的回合
                alice_score += aliceValues[idx]
            else:  # Bob 的回合
                bob_score += bobValues[idx]
        
        if alice_score > bob_score:
            return 1
        elif alice_score < bob_score:
            return -1
        else:
            return 0

public class Solution {
    public int StoneGameVI(int[] aliceValues, int[] bobValues) {
        int n = aliceValues.Length;
        var stones = new List<(int totalValue, int index)>();
        
        for (int i = 0; i < n; i++) {
            stones.Add((aliceValues[i] + bobValues[i], i));
        }
        
        stones.Sort((a, b) => b.totalValue.CompareTo(a.totalValue)); // 按总价值降序排序
        
        int aliceScore = 0, bobScore = 0;
        for (int i = 0; i < n; i++) {
            int idx = stones[i].index;
            if (i % 2 == 0) { // Alice 的回合
                aliceScore += aliceValues[idx];
            } else { // Bob 的回合
                bobScore += bobValues[idx];
            }
        }
        
        if (aliceScore > bobScore) return 1;
        else if (aliceScore < bobScore) return -1;
        else return 0;
    }
}

var stoneGameVI = function(aliceValues, bobValues) {
    const n = aliceValues.length;
    const stones = [];
    
    for (let i = 0; i < n; i++) {
        stones.push({
            index: i,
            totalValue: aliceValues[i] + bobValues[i],
            aliceValue: aliceValues[i],
            bobValue: bobValues[i]
        });
    }
    
    stones.sort((a, b) => b.totalValue - a.totalValue);
    
    let aliceScore = 0;
    let bobScore = 0;
    
    for (let i = 0; i < n; i++) {
        if (i % 2 === 0) {
            aliceScore += stones[i].aliceValue;
        } else {
            bobScore += stones[i].bobValue;
        }
    }
    
    if (aliceScore > bobScore) return 1;
    if (bobScore > aliceScore) return -1;
    return 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要时间消耗在排序操作上
空间复杂度O(n)需要存储石子的总价值和索引信息

相关题目