LeetCode 2706. 购买两块巧克力:一次遍历(O(n) + O(1))
【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 m1≤m2。
这样,我们只需要遍历价格数组,如果当前价格 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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!