leetcode
leetcode 1601 ~ 1650
雪糕的最大数量

雪糕的最大数量

难度:

标签:

题目描述

代码结果

运行时间: 81 ms, 内存: 27.0 MB


/*
 * Problem: Similar to the previous approach, we will use counting sort but in a more functional style using Java Streams.
 * We'll first count the frequencies, then sort and count the maximum ice creams that can be bought.
 */
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class MaxIceCreamStream {
    public int maxIceCream(int[] costs, int coins) {
        int maxCost = 100000;
        int[] count = new int[maxCost + 1];
        // Counting the frequency of each cost using streams
        IntStream.of(costs).forEach(cost -> count[cost]++);
        int[] totalIceCreams = {0};
        // Using streams to iterate through the costs
        IntStream.range(1, maxCost + 1).forEach(i -> {
            if (coins < i) return; // If remaining coins are less than the current cost, stop further processing
            if (count[i] == 0) return; // If no ice cream of this cost, skip
            int maxBuyable = Math.min(count[i], coins / i); // Max ice creams that can be bought at this cost
            totalIceCreams[0] += maxBuyable;
            coins -= maxBuyable * i; // Deduct the cost from the coins
        });
        return totalIceCreams[0];
    }
}

解释

方法:

该题解采用了计数排序的思路来解决问题。首先,通过遍历雪糕价格数组,统计每个价格雪糕的数量,将这些信息存储在一个频率数组中。然后,从最便宜的雪糕开始,依次检查Tony能否购买当前价格的所有雪糕。如果可以,则更新剩余的金钱和已购买的雪糕数量;如果不可以,则计算在当前价格下,Tony最多能购买多少雪糕,并更新已购买的雪糕数量。这个过程一直进行,直到金钱用尽或检查完所有价格的雪糕。

时间复杂度:

O(n + N)

空间复杂度:

O(N)

代码细节讲解

🦆
为什么选择计数排序来解决这个问题,而不是其他排序算法如快速排序或归并排序?
计数排序在这个问题中被选择是因为它非常适合处理有限范围的整数数据。由于雪糕价格的范围通常不会非常广泛,计数排序可以在O(n + k)的时间内完成排序,其中n是雪糕的数量,k是价格的范围。相比之下,快速排序或归并排序通常需要O(n log n)的时间。此外,计数排序直接给出了每个价格的雪糕数量,便于后续直接根据价格和数量计算最大可购买数量,而不需要额外的数据结构或步骤。
🦆
在代码中,如果coins的值非常小,小于costs数组中的任何一个元素,这个算法的表现如何?
如果coins的值非常小,甚至小于costs数组中的任何一个元素,算法仍然可以正确处理。在这种情况下,算法会从最便宜的雪糕开始尝试购买,但由于coins小于任何雪糕的价格,循环中的购买条件不会满足,因此购买数量ans将保持为0,代表没有购买任何雪糕。这体现了算法能够正确处理边界情况。
🦆
算法在处理所有价格的雪糕被购买完后,coins还有剩余的情况如何处理?是否存在未充分利用coins的情况?
算法确保每种雪糕都尽可能多地被购买,直到雪糕或金钱用尽为止。在遍历完所有价格后,如果coins还有剩余,此时已没有更多雪糕可以购买,因此金钱的剩余是不可避免的。由于算法从最便宜的雪糕开始购买,因此已尽最大努力用最小的花费获取最多的雪糕,没有更好的方法来进一步利用剩余的coins,除非有更便宜的雪糕可以购买。
🦆
如果在costs数组中存在多个高频但价格昂贵的雪糕,这种算法处理的效率和效果如何?
当costs数组中存在多个高频但价格昂贵的雪糕时,这种算法的效率依然是高效的,因为计数排序和随后的购买逻辑的时间复杂性仍然保持不变。然而,从效果上讲,由于这些雪糕价格较高,如果coins不足以购买足够数量的昂贵雪糕,那么可能无法最大化利用所有的coins来购买更多数量的雪糕。这种情况下,雪糕的购买数量可能会比拥有更多便宜雪糕的情况少。

相关问题