1833. 雪糕的最大数量（中）

夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。

商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。

注意： Tony 可以按任意顺序购买雪糕。

给你价格数组 costs 和现金量 coins ，请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。

你必须使用计数排序解决此问题。

示例

示例 1：

输入：costs = [1,3,2,4,1], coins = 7
输出：4
解释：Tony 可以买下标为 0、1、2、4 的雪糕，总价为 1 + 3 + 2 + 1 = 7

示例 2：

输入：costs = [10,6,8,7,7,8], coins = 5
输出：0
解释：Tony 没有足够的钱买任何一支雪糕。

示例 3：

输入：costs = [1,6,3,1,2,5], coins = 20
输出：6
解释：Tony 可以买下所有的雪糕，总价为 1 + 6 + 3 + 1 + 2 + 5 = 18

解法：计数排序

特点：不生成 sortedArr，直接在频次数组上遍历并结算，无法保证相对顺序。

var maxIceCreamSimple = function(costs, coins) {
    // 1. 找出价格最大值，确定计数数组范围
    let maxCost = 0;
    for (const cost of costs) {
        if (cost > maxCost) maxCost = cost;
    }

    // 2. 计数（频次统计）
    const freq = new Array(maxCost + 1).fill(0);
    for (const cost of costs) {
        freq[cost]++;
    }

    // 3. 直接遍历频次数组，从最便宜的雪糕开始买
    let ans = 0;
    for (let price = 1; price <= maxCost; price++) {
        // 如果当前价格都买不起，由于后面价格更贵，直接终止
        if (coins < price) break;

        const count = freq[price];
        if (count === 0) continue;

        // 一次性买完这个价格的所有雪糕（或仅买得起部分）
        const canBuy = Math.min(count, Math.floor(coins / price));
        ans += canBuy;
        coins -= canBuy * price;

        if (coins === 0) break;
    }
    return ans;
};

以上的排序其实是计数排序的简单版，或者说不稳定版，这种排序无法保证排序元素的相对顺序，也就无法应用于对对象的排序，然而，这种算法可以通过额外构建前缀和的方式来进一步完善成稳定版的，方法如下：

以数组[4, 2, 2, 8, 3, 3, 1]举例，总体来说计数排序分为以下四步：

计数，创建一个覆盖原数组range的辅助数组，每遇到一个数字，就在对应索引位置+1，结果：0:0, 1:1, 2:2, 3:2, 4:1, 5:0, 6:0, 7:0, 8:1。
变形，在计数数组上，对元素进行累加,arr[i]+=arr[i-1]，构建出变形数组，结果： [0, 1, 3, 5, 6, 6, 6, 6, 7]，代表的是当前下标对应的元素排在第几位，0排在第0位（没有），1排在第一位，2排在第三位，3排在第五位，这里的位置，其实是最大的位置。
还原，从后往前遍历原数组item，在计数数组中查找对应的位置，并插入最终数组中。 eg：1，找到arr[1]为1，因此final[0]=1(将1放在最终数组的第一位)，同时arr[1]-=1,变成0。往前遍历，3,arr[3]=5，因此final[4]=3，arr[3]-=1，变成4，代表下一个3要放在第4位，这是保证稳定性的关键。

如果计数数组存的不是最大位置，而是最小位置(如[0,1,2,4,6,6,6,6,7])，然后还原的时候从前往后遍历，也能保证稳定性。

解法二:计数排序(稳定版)

/**
 * 稳定计数排序（经典版）
 * 特点：前缀和 + 反向遍历，保证稳定性，可排序对象
 */
function countingSortStable(arr, getKey = (item) => item) {
    if (arr.length === 0) return arr;

    // 1. 提取键值并找出范围
    const keys = arr.map(getKey);
    const max = Math.max(...keys);
    const min = Math.min(...keys);
    const range = max - min + 1;

    // 2. 频次统计
    const count = new Array(range).fill(0);
    for (const key of keys) {
        count[key - min]++;
    }

    // 3. 计算前缀和（变形为“结束位置边界+1”）
    for (let i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    // 4. 反向遍历原数组，填入输出数组（关键步骤）
    const output = new Array(arr.length);
    for (let i = arr.length - 1; i >= 0; i--) {
        const key = keys[i];
        const idx = count[key - min] - 1; // 找到实际存放位置
        output[idx] = arr[i];             // 放入整个元素（而不只是数字）
        count[key - min]--;               // 边界前移
    }

    return output;
}

// 测试（纯数字）
console.log(countingSortStable([4, 2, 2, 8, 3, 3, 1])); 
// 输出：[1, 2, 2, 3, 3, 4, 8]

// 测试（对象排序，展示稳定性）
const people = [
    { name: '张三', age: 2 },
    { name: '李四', age: 1 },
    { name: '王五', age: 2 }
];
const sortedPeople = countingSortStable(people, p => p.age);
console.log(sortedPeople.map(p => `${p.name}:${p.age}`));
// 输出：['李四:1', '张三:2', '王五:2']
// 注意：两个 age=2 的人，张三排在王五前面，原始顺序被保留！