[LeetCode] 每日一题 1561. 你可以获得的最大硬币数目
题目链接
题目描述
有 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 将取剩下的一堆
要最大化我们的收益,策略如下:
贪心策略:让Bob尽可能分到的硬币最少,同时保证我们分到的是当前剩余硬币中数量较大的那堆
实现方法:对硬币堆排序后,从最大值开始,每次选出三堆,依次分给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 分得最小值,间接优化我们的收益
通过排序和索引操作,轻松实现了硬币的分配过程
我的收获:
这题让我更加理解了贪心算法的本质:在每一步局部选择中,确保当前利益最大化,从而接近全局最优解
通过排序简化复杂问题的思路也值得借鉴,类似的贪心题目往往需要一个初始排序步骤
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。