购买两块巧克力
难度:
标签:
题目描述
You are given an integer array prices representing the prices of various chocolates in a store. You are also given a single integer money, which represents your initial amount of money.
You must buy exactly two chocolates in such a way that you still have some non-negative leftover money. You would like to minimize the sum of the prices of the two chocolates you buy.
Return the amount of money you will have leftover after buying the two chocolates. If there is no way for you to buy two chocolates without ending up in debt, return money. Note that the leftover must be non-negative.
Example 1:
Input: prices = [1,2,2], money = 3 Output: 0 Explanation: Purchase the chocolates priced at 1 and 2 units respectively. You will have 3 - 3 = 0 units of money afterwards. Thus, we return 0.
Example 2:
Input: prices = [3,2,3], money = 3 Output: 3 Explanation: You cannot buy 2 chocolates without going in debt, so we return 3.
Constraints:
2 <= prices.length <= 501 <= prices[i] <= 1001 <= money <= 100
代码结果
运行时间: 16 ms, 内存: 16.5 MB
/*
* 题目思路：
* 使用Java Stream API处理这个问题，我们可以先生成所有可能的巧克力组合的总价。
* 然后过滤出总价小于等于money的组合，最后找出能剩下的最多钱数。
*/
import java.util.*;
import java.util.stream.*;
public class ChocolateShoppingStream {
public static int maxMoneyLeft(int[] prices, int money) {
int maxRemaining = Arrays.stream(prices)
.boxed()
.flatMap(i -> Arrays.stream(prices).boxed().map(j -> i + j))
.filter(total -> total <= money)
.map(total -> money - total)
.max(Integer::compareTo)
.orElse(money);
return maxRemaining;
}
public static void main(String[] args) {
int[] prices1 = {1, 2, 2};
int money1 = 3;
System.out.println(maxMoneyLeft(prices1, money1)); // 输出：0
int[] prices2 = {3, 2, 3};
int money2 = 3;
System.out.println(maxMoneyLeft(prices2, money2)); // 输出：3
}
}解释
方法:
题目要求购买两块巧克力并最小化总花费以使得剩余的钱最多。首先，我们对价格数组进行排序。如果有足够的钱购买最便宜的两块巧克力（即排序后的前两个价格），则购买这两块巧克力，并计算剩余的钱。如果连最便宜的两块巧克力都买不起，则直接返回持有的钱数。
时间复杂度:
O(n log n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择对价格数组进行排序，而不是使用其他可能更高效的方法？
▷🦆
在排序后直接选择最便宜的两块巧克力是否总是保证剩余金钱最多？是否存在选择其他两块巧克力但剩余更多金钱的情况？
▷🦆
题解中提到如果连最便宜的两块巧克力都买不起则返回持有的钱数，这种情况下是否还有必要进行排序操作？
▷🦆
如果价格数组中存在多个相同的最低价格，题解中的方法是否考虑了这一点？
▷