文章

[LeetCode] 每日一题 1561. 你可以获得的最大硬币数目

题目链接

https://leetcode.cn/problems/maximum-number-of-coins-you-can-get

题目描述

有 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

解题思路

这是一道适合使用贪心算法解决的问题。题目要求我们在三个人分硬币的过程中,尽可能获得最大的硬币数。每轮分配规则如下:

  • Alice 总是取当前硬币堆中数量最多的一堆

  • 我们将取数量第二多的一堆

  • Bob 将取剩下的一堆

要最大化我们的收益,策略如下:

  1. 贪心策略:让Bob尽可能分到的硬币最少,同时保证我们分到的是当前剩余硬币中数量较大的那堆

  2. 实现方法:对硬币堆排序后,从最大值开始,每次选出三堆,依次分给Alice、我们和Bob。通过调整索引,可以模拟分配过程

具体实现如下:

  • 排序后,每次从数组末尾选出三堆:right - 1 分给我们,right 分给 Alice,left 分给 Bob

  • 更新索引:right 向左移动两次,left 向右移动一次

  • 累计我们获取的硬币数,直到数组被分配完

通过这种方式,我们总是取到数量尽可能大的硬币,最大化收益

代码实现

class Solution {
    public int maxCoins(int[] piles) {
        Arrays.sort(piles);
        int ans = 0, left = 0, right = piles.length - 1;
        while (left < right) {
            // Alice 取最大
            right--;
            // 我取第二大
            ans += piles[right--];
            // Bob 取最小
            left++;
        }
        return ans;
    }
}

复杂度分析

  • 时间复杂度

    • 排序的时间复杂度为 O(n log n),其中 n 是硬币堆的数量

    • 遍历数组的时间复杂度为 O(n)

    • 综合时间复杂度为 O(n log n)

  • 空间复杂度

    • 排序算法通常需要 O(log n) 的栈空间

    • 整体没有引入额外的空间,因此综合空间复杂度为 O(log n)

总结

这道题通过贪心算法很好地体现了在限制条件下的最优策略选择:

  • 我们无法改变 Alice 总是取最大值的规则,因此需要通过控制 Bob 分得最小值,间接优化我们的收益

  • 通过排序和索引操作,轻松实现了硬币的分配过程

我的收获:

  • 这题让我更加理解了贪心算法的本质:在每一步局部选择中,确保当前利益最大化,从而接近全局最优解

  • 通过排序简化复杂问题的思路也值得借鉴,类似的贪心题目往往需要一个初始排序步骤

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0