Medium

题目描述

有 3n 堆硬币，大小各不相同。你和你的朋友们将按照以下方式取硬币堆：

  • 在每一步中，你将选择任意 3 堆硬币（不一定是连续的）。
  • 在你的选择中，Alice 将选择硬币数量最多的那堆。
  • 你将选择硬币数量第二多的那堆。
  • 你的朋友 Bob 将选择最后一堆。
  • 重复上述步骤，直到没有更多硬币堆。

给你一个整数数组 piles，其中 piles[i] 是第 i 堆硬币的数目。

返回你能获得的最大硬币数目。

示例 1：

输入：piles = [2,4,1,2,7,8]
输出：9
解释：选择三元组 (2, 7, 8)，Alice 选择有 8 个硬币的堆，你选择有 7 个硬币的堆，Bob 选择最后一堆。
选择三元组 (1, 2, 4)，Alice 选择有 4 个硬币的堆，你选择有 2 个硬币的堆，Bob 选择最后一堆。
你能获得的最大硬币数目：7 + 2 = 9。
另一方面，如果我们选择这样的安排 (1, 2, 8), (2, 4, 7)，你只能得到 2 + 4 = 6 个硬币，这不是最优的。

示例 2：

输入：piles = [2,4,5]
输出：4

示例 3：

输入：piles = [9,8,7,6,5,1,2,3,4]
输出：18

约束条件：

  • 3 <= piles.length <= 10^5
  • piles.length % 3 == 0
  • 1 <= piles[i] <= 10^4

提示：

  • 你永远无法拿到哪堆硬币？
  • 无论如何，Bob 都被迫拿最后一堆硬币。你应该给他哪一堆？

解题思路

这道题的关键在于理解游戏策略和如何最大化自己的收益。

核心观察：

  1. 每轮游戏中，Alice总是拿最大的，你拿第二大的，Bob拿最小的
  2. 由于Bob总是拿最小的，我们应该尽可能让他拿到最小的硬币堆
  3. 为了让自己拿到尽可能多的硬币，应该让自己在每轮中都拿到相对较大的数值

贪心策略： 最优策略是将所有硬币堆按降序排列，然后：

  • 将最小的 n 堆硬币都给 Bob（这些是我们永远拿不到的）
  • 在剩余的 2n 堆中，按照 (最大, 次大) 的模式分组
  • 每组中 Alice 拿最大的，我们拿次大的

具体实现：

  1. 将数组降序排序
  2. 跳过前 n 个最小的元素（这些注定给 Bob）
  3. 从剩余元素中，每隔一个取一个元素（即取第二大的位置）

推荐解法： 排序 + 贪心策略，时间复杂度最优。

代码实现

class Solution {
public:
    int maxCoins(vector<int>& piles) {
        sort(piles.begin(), piles.end(), greater<int>());
        int n = piles.size() / 3;
        int result = 0;
        
        for (int i = 1; i < 2 * n; i += 2) {
            result += piles[i];
        }
        
        return result;
    }
};

class Solution:
    def maxCoins(self, piles: List[int]) -> int:
        piles.sort(reverse=True)
        n = len(piles) // 3
        result = 0
        
        for i in range(1, 2 * n, 2):
            result += piles[i]
            
        return result

public class Solution {
    public int MaxCoins(int[] piles) {
        Array.Sort(piles, (a, b) => b.CompareTo(a));
        int n = piles.Length / 3;
        int result = 0;
        
        for (int i = 1; i < 2 * n; i += 2) {
            result += piles[i];
        }
        
        return result;
    }
}

var maxCoins = function(piles) {
    piles.sort((a, b) => b - a);
    const n = Math.floor(piles.length / 3);
    let result = 0;
    
    for (let i = 1; i < 2 * n; i += 2) {
        result += piles[i];
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n log n)主要开销在排序操作
空间复杂度O(1)只使用常数级额外空间（原地排序）