你可以获得的最大硬币数目

难度: 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

Submission

运行时间: 103 ms

内存: 25.8 MB

class Solution:
    def maxCoins(self, piles: List[int]) -> int:
        piles.sort()
        nums=0
        length=len(piles)
        n=length//3  #前n个数 作为最后一项
        # 981 762 543
        for i in range(n,length,2):
            nums+=piles[i]
        return nums

Explain

首先对硬币堆数组进行排序。这样，最大的数总是在数组的尾部，最小的数在数组的头部。按题目规定，每轮选取三堆硬币时，Alice取最多的，你取第二多的，Bob取最少的。为了最大化你的得分，理想的策略是让Alice和Bob分别拿走数组中两端的硬币，而你则总是从中间取硬币。具体操作是，首先排除前n堆最小的硬币（这些硬币在排序后数组的前n个位置，将被Bob拿走），然后从数组中间部分开始，每次跳过一堆（即，每次取排序后数组中从倒数第二组开始向前数的每第二个硬币堆），直到取完所有硬币。这样做可以确保你每次都取到每组三堆中的中间一堆，从而最大化你从每轮获取的硬币数量。

时间复杂度: O(n log n)

空间复杂度: O(1)

# 定义一个类 Solution 包含函数 maxCoins

class Solution:
    def maxCoins(self, piles: List[int]) -> int:
        # 首先对硬币堆进行排序
        piles.sort()
        # 初始化用于存放你的硬币总数的变量
        nums = 0
        # 计算piles数组的长度
        length = len(piles)
        # 计算前n个最小的元素的数量（Bob将会取走这些）
        n = length // 3
        # 从倒数第二个元素开始，每次跳过一元素（即跳过Alice拿的那堆），累加得到你的硬币数
        for i in range(n, length, 2):
            nums += piles[i]
        # 返回你可以获得的最大硬币数目
        return nums

Explore

在每轮中，Alice, 你, 和 Bob 分别从最多到最少拿取硬币，因此排序后的数组中，最大的硬币数目在最末尾。每轮取三堆时，为了确保你每次都取到每组三堆中硬币数第二多的一堆，你应该从数组的倒数第二个开始取，因为Alice会取走最后一堆（即最大的一堆）。这样，从倒数第二个开始取，然后每次跳过两个（一堆是Bob的，一堆是Alice的），可以保证你在每一轮中都取到中间数量的硬币。

在排序后的硬币堆数组中，从倒数第二个开始取，并每次向前跳过两堆（即每轮Alice和Bob各自取走的一堆），可以确保你每次取到的都是剩余硬币堆中第二多的硬币堆。这种跳跃方式符合游戏规则，即Alice取最多，你取第二多，Bob取最少，故通过这种间隔跳跃的方法可以确保你总是取到中间数量的硬币。

将前n个最小的元素排除是在当前游戏规则下的最优策略，因为这样做可以最大化你从每组硬币中获取的数量。这种策略假设Bob总是从剩余最小的一堆中拿取硬币，确保Alice和你能拿到更多的硬币。在不同的游戏规则或不同的目标下（如总硬币数最大化而不是个人最大化），可能会有不同的策略更为合适。

使用排序的方法可以直观且一次性地确定所有硬币堆的顺序，便于实现按照游戏规则从大到小顺序取硬币的逻辑。虽然使用最大堆或最小堆可以动态管理硬币堆的大小关系，但在本题中，需要同时考虑最大、最小及中间大小的硬币堆，堆结构不如排序来得直接和高效。排序一次后按需索引即可获得任何位置的硬币堆，而堆结构则需要多次调整来获取不同位置的硬币堆，效率较低。