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

Categories:

题目描述
思路分析
1. 解法一：排序 + 贪心（推荐）
相似题目

题目描述

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

思路分析

解法一：排序 + 贪心（推荐）

核心思路：

共有 3n 个硬币，每轮从中选 3 枚，Alice 拿最大的，我们拿第二大的，Bob 拿最小的

为了让我们拿到尽可能多的硬币，应让 Bob 每次拿最小的硬币，这样我们可以拿第二大的

排序后，Bob 依次拿走最小的 n 枚（索引 0 到 n-1），剩余 2n 枚按从大到小每两个取第一个即为我们能拿到的

即排序后，从索引 n 开始，每隔一个取一次：arr[n], arr[n+2], arr[n+4], ...，共取 n 次

复杂度分析：

时间复杂度：O(n log n)，其中 n 为数组长度（即 piles.length/3）

空间复杂度：O(log n)，排序递归栈空间

class Solution {
    public int maxCoins(int[] piles) {
        Arrays.sort(piles);

        int n = piles.length / 3;
        int result = 0;

        // 从第 n 个元素开始，每隔一个取一次（我们取第二大的）
        for (int i = n; i < piles.length; i += 2) {
            result += piles[i];
        }

        return result;
    }
}

func maxCoins(piles []int) int {
    sort.Ints(piles)

    n := len(piles) / 3
    result := 0

    // 从第 n 个元素开始，每隔一个取一次（我们取第二大的）
    for i := n; i < len(piles); i += 2 {
        result += piles[i]
    }

    return result
}

相似题目

题目	难度	考察点
1403. 非递增顺序的最小子序列	简单	排序 + 贪心
881. 救生艇	中等	排序 + 贪心 + 双指针
455. 分发饼干	简单	排序 + 贪心
2144. 打折购买糖果的最小开销	简单	排序 + 贪心
1196. 最多可以买到的苹果数量	简单	排序 + 贪心
976. 三角形的最大周长	简单	排序 + 贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/25528552