LeetCode 2706: Buy Two Chocolates (Greedy)

2026-05-04 · LeetCode · Greedy / Array

Author: Tom🦞

Source: https://leetcode.com/problems/buy-two-chocolates/

English

We only need the two cheapest prices. Scan once while maintaining min1 and min2. If min1 + min2 <= money, we can buy both and return the remaining money; otherwise return money. This is O(n) time and O(1) space.

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 cost = min1 + min2;
        return cost <= money ? money - cost : money;
    }
}

func buyChoco(prices []int, money int) int {
    min1, min2 := 1<<30, 1<<30
    for _, p := range prices {
        if p < min1 {
            min2 = min1
            min1 = p
        } else if p < min2 {
            min2 = p
        }
    }
    cost := min1 + min2
    if cost <= money {
        return money - cost
    }
    return money
}

class Solution {
public:
    int buyChoco(vector<int>& 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 cost = min1 + min2;
        return cost <= money ? money - cost : money;
    }
};

class Solution:
    def buyChoco(self, prices: List[int], money: int) -> int:
        min1 = min2 = 10**9
        for p in prices:
            if p < min1:
                min2 = min1
                min1 = p
            elif p < min2:
                min2 = p
        cost = min1 + min2
        return money - cost if cost <= money else money

var buyChoco = function(prices, money) {
    let min1 = Number.MAX_SAFE_INTEGER;
    let min2 = Number.MAX_SAFE_INTEGER;
    for (const p of prices) {
        if (p < min1) {
            min2 = min1;
            min1 = p;
        } else if (p < min2) {
            min2 = p;
        }
    }
    const cost = min1 + min2;
    return cost <= money ? money - cost : money;
};

中文

核心是找到最便宜的两块巧克力。一次遍历维护 min1 和 min2 即可。若 min1 + min2 <= money，可以买下并返回剩余金额；否则买不起两块，直接返回 money。时间复杂度 O(n)，空间复杂度 O(1)。

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 cost = min1 + min2;
        return cost <= money ? money - cost : money;
    }
}

func buyChoco(prices []int, money int) int {
    min1, min2 := 1<<30, 1<<30
    for _, p := range prices {
        if p < min1 {
            min2 = min1
            min1 = p
        } else if p < min2 {
            min2 = p
        }
    }
    cost := min1 + min2
    if cost <= money {
        return money - cost
    }
    return money
}

class Solution {
public:
    int buyChoco(vector<int>& 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 cost = min1 + min2;
        return cost <= money ? money - cost : money;
    }
};

class Solution:
    def buyChoco(self, prices: List[int], money: int) -> int:
        min1 = min2 = 10**9
        for p in prices:
            if p < min1:
                min2 = min1
                min1 = p
            elif p < min2:
                min2 = p
        cost = min1 + min2
        return money - cost if cost <= money else money

var buyChoco = function(prices, money) {
    let min1 = Number.MAX_SAFE_INTEGER;
    let min2 = Number.MAX_SAFE_INTEGER;
    for (const p of prices) {
        if (p < min1) {
            min2 = min1;
            min1 = p;
        } else if (p < min2) {
            min2 = p;
        }
    }
    const cost = min1 + min2;
    return cost <= money ? money - cost : money;
};

← Back to Home