LeetCode 2706 Buy Two Chocolates 详解：从暴力枚举到 O(n) 贪心的三种解法

LeetCode 2706 Buy Two Chocolates 详解从暴力枚举到 O(n) 贪心的三种解法【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode给定价格数组与预算如何用最少的钱买下两块巧克力并最大化剩余金额这道题是理解贪心算法与数组最小元素维护的经典入门题。本文以本仓库 articles/buy-two-chocolates.md 为核心脉络完整覆盖暴力枚举、排序取前二、单次遍历贪心三种解法并给出 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言的完整可运行代码与复杂度分析。读完你不仅能一次 AC 本题还能掌握在一趟扫描中维护前 k 个最小值这一可复用于 Top K 类问题的通用技巧。前置知识在动手解题之前建议先确认自己对以下三个基础点足够熟悉数组Arrays能够熟练遍历数组并通过下标访问元素排序Sorting理解排序的机制及其时间复杂度贪心算法Greedy Algorithms理解做出局部最优选择以逼近全局最优的核心思想——本题中买最便宜的两块巧克力正是典型的局部最优即全局最优场景。问题重述与题意分析buyChoco(prices, money)接收两块信息prices整数数组prices[i]表示第i块巧克力的价格money当前拥有的总金额。要求恰好购买两块不同的巧克力并返回购买后剩余的最大金额如果任何两块巧克力的价格之和都超过预算则什么都不买直接返回money。关键约束可归纳为两点必须买两块不能只买一块买不起就不买——返回原金额而不是负数或 0。由于要最大化剩余金额等价于最小化两块巧克力的总花费因此问题最终收敛为找到数组中最便宜的两个价格检查其总和是否在预算内。这正是三种解法共同的优化目标。方法一暴力枚举Brute Force核心直觉最直接的想法枚举所有可能的巧克力对(i, j)要求i j以避免重复逐一判断两块的价和是否不超过预算若是则计算money - prices[i] - prices[j]作为剩余金额并持续更新最大值。若最终没有找到任何合法组合说明预算连最便宜的两块都买不起返回money。算法步骤初始化结果res -1表示尚未找到合法购买组合双层循环枚举所有对(i, j)且i j若prices[i] prices[j] money计算剩余金额并更新res为历史最大值循环结束后若res -1无合法组合返回money什么都不买否则返回最大剩余金额res。多语言实现class Solution: def buyChoco(self, prices: List[int], money: int) - int: res -1 for i in range(len(prices)): for j in range(i 1, len(prices)): if prices[i] prices[j] money: res max(res, money - prices[i] - prices[j]) return res if res ! -1 else moneypublic class Solution { public int buyChoco(int[] prices, int money) { int res -1; for (int i 0; i prices.length; i) { for (int j i 1; j prices.length; j) { if (prices[i] prices[j] money) { res Math.max(res, money - prices[i] - prices[j]); } } } return res -1 ? money : res; } }class Solution { public: int buyChoco(vectorint prices, int money) { int res -1; for (int i 0; i prices.size(); i) { for (int j i 1; j prices.size(); j) { if (prices[i] prices[j] money) { res max(res, money - prices[i] - prices[j]); } } } return res -1 ? money : res; } };class Solution { /** * param {number[]} prices * param {number} money * return {number} */ buyChoco(prices, money) { let res -1; for (let i 0; i prices.length; i) { for (let j i 1; j prices.length; j) { if (prices[i] prices[j] money) { res Math.max(res, money - prices[i] - prices[j]); } } } return res -1 ? money : res; } }public class Solution { public int BuyChoco(int[] prices, int money) { int res -1; for (int i 0; i prices.Length; i) { for (int j i 1; j prices.Length; j) { if (prices[i] prices[j] money) { res Math.Max(res, money - prices[i] - prices[j]); } } } return res -1 ? money : res; } }func buyChoco(prices []int, money int) int { res : -1 for i : 0; i len(prices); i { for j : i 1; j len(prices); j { if prices[i]prices[j] money { if money-prices[i]-prices[j] res { res money - prices[i] - prices[j] } } } } if res -1 { return money } return res }class Solution { fun buyChoco(prices: IntArray, money: Int): Int { var res -1 for (i in prices.indices) { for (j in i 1 until prices.size) { if (prices[i] prices[j] money) { res maxOf(res, money - prices[i] - prices[j]) } } } return if (res -1) money else res } }class Solution { func buyChoco(_ prices: [Int], _ money: Int) - Int { var res -1 for i in 0..prices.count { for j in (i 1)..prices.count { if prices[i] prices[j] money { res max(res, money - prices[i] - prices[j]) } } } return res -1 ? money : res } }impl Solution { pub fn buy_choco(prices: Veci32, money: i32) - i32 { let mut res -1; for i in 0..prices.len() { for j in (i 1)..prices.len() { if prices[i] prices[j] money { res res.max(money - prices[i] - prices[j]); } } } if res -1 { money } else { res } } }复杂度分析时间复杂度$O(n^2)$——双层循环枚举全部 $\frac{n(n-1)}{2}$ 个组合空间复杂度$O(1)$——仅使用常数个额外变量。暴力法思路简单、不易出错但 $n$ 较大时不可接受适合作为验证正确性的参照实现。方法二排序取前二Sorting核心直觉要最小化总花费就应该买最便宜的两块。排序后数组升序排列最便宜的两块必然位于数组开头下标 0 和 1。因此只需判断prices[0] prices[1]是否不超过money一步即可得出答案完全不需要枚举所有组合。算法步骤将prices按升序排序计算buy prices[0] prices[1]即最便宜两块的总价若buy money返回money买不起什么都不买否则返回money - buy。多语言实现class Solution: def buyChoco(self, prices: List[int], money: int) - int: prices.sort() buy prices[0] prices[1] return money if buy money else money - buypublic class Solution { public int buyChoco(int[] prices, int money) { Arrays.sort(prices); int buy prices[0] prices[1]; return buy money ? money : money - buy; } }class Solution { public: int buyChoco(vectorint prices, int money) { sort(prices.begin(), prices.end()); int buy prices[0] prices[1]; return buy money ? money : money - buy; } };class Solution { /** * param {number[]} prices * param {number} money * return {number} */ buyChoco(prices, money) { prices.sort((a, b) a - b); let buy prices[0] prices[1]; return buy money ? money : money - buy; } }public class Solution { public int BuyChoco(int[] prices, int money) { Array.Sort(prices); int buy prices[0] prices[1]; return buy money ? money : money - buy; } }func buyChoco(prices []int, money int) int { sort.Ints(prices) buy : prices[0] prices[1] if buy money { return money } return money - buy }class Solution { fun buyChoco(prices: IntArray, money: Int): Int { prices.sort() val buy prices[0] prices[1] return if (buy money) money else money - buy } }class Solution { func buyChoco(_ prices: [Int], _ money: Int) - Int { let sorted prices.sorted() let buy sorted[0] sorted[1] return buy money ? money : money - buy } }impl Solution { pub fn buy_choco(mut prices: Veci32, money: i32) - i32 { prices.sort(); let buy prices[0] prices[1]; if buy money { money } else { money - buy } } }复杂度分析时间复杂度$O(n \log n)$——主要开销来自排序空间复杂度$O(1)$ 或 $O(n)$——取决于所用排序算法的实现如原地快排为 $O(1)$ 辅助空间归并排序为 $O(n)$。排序法代码极短是最易读的工程实现。需要注意的是它修改了传入的prices数组原地排序若题目要求保持原数组不变则需自行复制或在方法三的单遍扫描方案间取舍。方法三贪心Greedy单次遍历核心直觉排序其实做了大量多余工作——我们只关心最小的两个数。既然目标只是找两个最小值就可以不排序、单次遍历完成边遍历边维护已见元素中最小的两个遍历结束后这两个值就是全局最小的两块巧克力价格。这是一种典型的贪心思想每一步都只关心当前最优的两个候选无需全局重排。算法步骤初始化两个变量min1最小价格与min2第二小价格均置为无穷大inf/INT_MAX/Integer.MAX_VALUE等遍历每个价格p若p min1说明出现了新的最小值先将旧的min1降级为min2再令min1 p否则若p min2说明它是当前第二小的候选令min2 p计算leftover money - min1 - min2若leftover 0返回leftover否则返回money买不起则什么都不买。多语言实现class Solution: def buyChoco(self, prices: list[int], money: int) - int: min1 min2 float(inf) for p in prices: if p min1: min1, min2 p, min1 elif p min2: min2 p leftover money - min1 - min2 return leftover if leftover 0 else moneypublic class Solution { public int buyChoco(int[] prices, int money) { int min1 Integer.MAX_VALUE, min2 Integer.MAX_VALUE; for (int p : prices) { if (p min1) { min2 min1; min1 p; } else if (p min2) { min2 p; } } int leftover money - min1 - min2; return leftover 0 ? leftover : money; } }class Solution { public: int buyChoco(vectorint prices, int money) { int min1 INT_MAX, min2 INT_MAX; for (int p : prices) { if (p min1) { min2 min1; min1 p; } else if (p min2) { min2 p; } } int leftover money - min1 - min2; return leftover 0 ? leftover : money; } };class Solution { /** * param {number[]} prices * param {number} money * return {number} */ buyChoco(prices, money) { let min1 Infinity, min2 Infinity; for (const p of prices) { if (p min1) { min2 min1; min1 p; } else if (p min2) { min2 p; } } const leftover money - min1 - min2; return leftover 0 ? leftover : money; } }public class Solution { public int BuyChoco(int[] prices, int money) { int min1 int.MaxValue, min2 int.MaxValue; foreach (int p in prices) { if (p min1) { min2 min1; min1 p; } else if (p min2) { min2 p; } } int leftover money - min1 - min2; return leftover 0 ? leftover : money; } }func buyChoco(prices []int, money int) int { min1, min2 : math.MaxInt32, math.MaxInt32 for _, p : range prices { if p min1 { min2 min1 min1 p } else if p min2 { min2 p } } leftover : money - min1 - min2 if leftover 0 { return leftover } return money }class Solution { fun buyChoco(prices: IntArray, money: Int): Int { var min1 Int.MAX_VALUE var min2 Int.MAX_VALUE for (p in prices) { if (p min1) { min2 min1 min1 p } else if (p min2) { min2 p } } val leftover money - min1 - min2 return if (leftover 0) leftover else money } }class Solution { func buyChoco(_ prices: [Int], _ money: Int) - Int { var min1 Int.max var min2 Int.max for p in prices { if p min1 { min2 min1 min1 p } else if p min2 { min2 p } } let leftover money - min1 - min2 return leftover 0 ? leftover : money } }impl Solution { pub fn buy_choco(prices: Veci32, money: i32) - i32 { let (mut min1, mut min2) (i32::MAX, i32::MAX); for p in prices { if p min1 { min2 min1; min1 p; } else if p min2 { min2 p; } } let leftover money - min1 - min2; if leftover 0 { leftover } else { money } } }复杂度分析时间复杂度$O(n)$——仅需一趟线性扫描空间复杂度$O(1)$——只使用两个额外变量。这是本题的最优解不排序、不改动原数组、不占用额外空间而且一趟维护前 k 个最小/最大值的模式可以无缝推广到数组中第 k 小元素滑动窗口 Top K等更多场景。三种方法对比一览方法核心思路时间复杂度空间复杂度是否修改原数组暴力枚举枚举所有二元组(i, j)更新最大剩余$O(n^2)$$O(1)$否排序取前二升序排序后取前两个元素$O(n \log n)$$O(1)$ 或 $O(n)$是原地排序时贪心单遍扫描一趟维护min1、min2两个最小值$O(n)$$O(1)$否三者正确性一致复杂度逐级递减面试或刷题场景中优先掌握方法三的写法同时能清晰解释方法一的正确性与方法二的简洁性。常见陷阱陷阱一买不起两块时返回了负数剩余如果最便宜两块的总价超过预算正确行为是什么都不买、原样返回money而不是返回负数或 0。# Wrong: returning negative leftover return money - min1 - min2 # Could be negative # Correct: check if affordable first对应到三种解法中暴力法用res -1哨兵值区分无合法组合排序法与贪心法用buy money或leftover 0显式判断。陷阱二更新最小值时丢失了旧的min1当发现新的最小价格时如果只更新min1而不把旧的最小值降级为min2就会丢掉一个合法候选导致结果错误。# Wrong: losing second minimum if p min1: min1 p # min2 is never updated with old min1正确的更新顺序必须是先把旧min1赋给min2再把新值写入min1即先保存、后覆盖。同理Java 版本的另一种等价写法见下节源码先用p min2做外层判断再在内部细分p min1同样能保证两个最小值被正确维护。仓库源码印证多语言实现对照本仓库中该题编号为2706与本文三种解法对应的实现分散在多个语言目录中可作为额外的参考与验证JavaScript 实现注释标注为Greedy | Array时间复杂度 $O(n)$、空间复杂度 $O(1)$。其写法另辟蹊径——先splice出当前最小值作为cheapestChocolate再次splice出剩余部分的最小值作为secondCheapestChocolate最后用leftOverMoney -1 ? leftOverMoney : money处理买不起的情况与本文贪心法殊途同归Java 实现同一文件内给出了两份解——一份 $O(n)$ 贪心外层p min2、内层细分p min1的嵌套写法一份 $O(n \log n)$ 排序解与本文方法二、方法三一一对应Kotlin 实现$O(n)$ 单遍扫描实现else分支中通过minOf(min2, p)更新第二小值是与本文贪心等价的另一种写法。从这些实现可以看出同一算法思想在不同语言、不同代码风格下可以有多种等价表达但核心不变维护两个最小值判断买得起与否。你可以对照阅读 articles/buy-two-chocolates.md 与上述源码加深对三种解法的理解。小结本题的价值不在于买巧克力本身而在于它串联起了三个层层递进的能力点用暴力枚举建立正确性基线用排序换取代码极简用贪心单遍扫描达到 $O(n)$ 时间、$O(1)$ 空间的最优解并掌握一趟维护前 k 个最值这一可迁移的核心套路。下次遇到在数组里找最小的两个/最大的几个元素或能否用最低成本完成某组合这类问题时你可以在几秒钟内定位到本题的贪心模板直接套用。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考