LeetCode 2706. 购买两块巧克力:一次遍历(O(n) + O(1))

2023-12-29 18:48:38

【LetMeFly】2706.购买两块巧克力:一次遍历(O(n) + O(1))

力扣题目链接:https://leetcode.cn/problems/buy-two-chocolates/

给你一个整数数组?prices?,它表示一个商店里若干巧克力的价格。同时给你一个整数?money?,表示你一开始拥有的钱数。

你必须购买 恰好?两块巧克力,而且剩余的钱数必须是 非负数?。同时你想最小化购买两块巧克力的总花费。

请你返回在购买两块巧克力后,最多能剩下多少钱。如果购买任意两块巧克力都超过了你拥有的钱,请你返回 money?。注意剩余钱数必须是非负数。

?

示例 1:

输入:prices = [1,2,2], money = 3
输出:0
解释:分别购买价格为 1 和 2 的巧克力。你剩下 3 - 3 = 0 块钱。所以我们返回 0 。

示例 2:

输入:prices = [3,2,3], money = 3
输出:3
解释:购买任意 2 块巧克力都会超过你拥有的钱数,所以我们返回 3 。

?

提示:

  • 2 <= prices.length <= 50
  • 1 <= prices[i] <= 100
  • 1 <= money <= 100

方法一:一次遍历

使用两个变量 m 1 m1 m1 m 2 m2 m2来维护“最便宜的两块巧克力的价格”,并且保证,在每次操作结束后满足 m 1 ≤ m 2 m1\leq m2 m1m2

这样,我们只需要遍历价格数组,如果当前价格 p < m 2 p\lt m2 p<m2,则说明这个价格具有“利用价值”,令 m 2 = p m2=p m2=p。如果 m 1 > m 2 m1\gt m2 m1>m2,则交换二者。

遍历结束后我们便得到了价格最低的两块巧克力。

  • 时间复杂度 O ( l e n ( p r i c e s ) ) O(len(prices)) O(len(prices))
  • 空间复杂度 O ( 1 ) O(1) O(1)

AC代码

C++
class Solution {
public:
    int buyChoco(vector<int>& prices, int money) {
        int m1 = 1000, m2 = 1000;  // 令m1 <= m2
        for (int p : prices) {
            if (p < m2) {
                m2 = p;
                if (m1 > m2) {
                    swap(m1, m2);
                }
            }
        }
        return m1 + m2 > money ? money : money - m1 - m2;
    }
};
Python
from typing import List

class Solution:
    def buyChoco(self, prices: List[int], money: int) -> int:
        m1, m2 = 1000, 1000
        for p in prices:
            if p < m2:
                m2 = p
                if m1 > m2:
                    m1, m2 = m2, m1
        return money if m1 + m2 > money else money - m1 - m2

同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/135295305

文章来源:https://blog.csdn.net/Tisfy/article/details/135295305
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。