代码训练(15)LeetCode之买卖股票
Author: Once Day Date: 2024年4月22日
漫漫长路,才刚刚开始…
全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客
参考文章:
- 122. 买卖股票的最佳时机 II - 力扣(LeetCode)
- 力扣 (LeetCode) 全球极客挚爱的技术成长平台
1. 原题
给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。
在每一天,你可以决定是否购买和/或出售股票。你在任何时候最多只能持有 一股 股票。你也可以先购买,然后在同一天出售。
返回你能获得的最大利润 。
例如对于prices = [7,1,5,3,6,4]
,最大利润为7,即:
- 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
- 随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
- 总利润为 4 + 3 = 7 。
2. 分析
这道题需要找出在给定股票价格数组 prices
中能获得的最大利润,其中 prices[i]
代表第 i
天的股票价格。规则是在任何一天,可以决定是否购买或者出售股票,但最多只能持有一股股票,并且允许在同一天买入和卖出。题目要求返回可能的最大利润。
关键在于理解在哪些天买入和在哪些天卖出可以获得最大利润。由于可以在同一天买入和卖出,那么只要今天的价格比昨天高,就可以认为昨天买入,今天卖出是有利可图的。
具体策略是:
- 遍历价格数组,从第二天开始比较。
- 每当发现今天的价格比昨天的高,就计算这一天的利润(今天的价格减去昨天的价格),并累加到总利润中。
这种策略的好处在于不需要维护任何复杂的状态,只需要在价格上升的时候“买卖”即可。
分析步骤:
- 初始化一个变量
maxProfit
来存储总利润,初值设为0。 - 从第二天开始遍历价格数组。
- 对于每一天,如果价格比前一天高,就将差价加到
maxProfit
上。 - 最后返回
maxProfit
。
性能优化关键点:
- 执行速度:这个算法的时间复杂度是 O(n),因为只需要遍历一次价格数组,这是非常高效的。
- 内存使用:空间复杂度为 O(1),因为我们只使用了常数额外空间。
3. 代码实现
int maxProfit(int* prices, int pricesSize) {
int32_t i, state, money, buy_price, last_price;
state = 1; /* 买入 */
money = 0;
last_price = buy_price = prices[0];
for (i = 1; i < pricesSize; i++) {
if (prices[i] < last_price) {
/* 降价卖出 */
if (state) {
money += last_price - buy_price;
state = 0;
}
} else if (prices[i] > last_price) {
/* 升价买入 */
if (!state) {
buy_price = last_price;
state = 1;
}
}
last_price = prices[i];
}
/* 最后直接卖掉 */
if (state) {
money += last_price - buy_price;
}
return money;
}
这段代码实现了一个简单的股票交易策略,目标是最大化利润。函数的输入是一个整数数组 prices
,表示一段时间内股票的价格变化,数组的大小为 pricesSize
。
代码的主要逻辑如下:
-
初始化变量:
state
表示当前的交易状态,1 表示持有股票(买入),0 表示不持有股票(卖出),money
表示当前的总利润,buy_price
表示最近一次买入的价格,last_price
表示上一次的股票价格。 -
遍历价格数组,从下标 1 开始:
- 如果当前价格小于上一次的价格(降价):
- 如果当前持有股票(
state
为 1),则卖出股票,计算利润并更新money
,将state
设为 0。
- 如果当前持有股票(
- 如果当前价格大于上一次的价格(升价):
- 如果当前不持有股票(
state
为 0),则买入股票,将buy_price
设为上一次的价格,将state
设为 1。
- 如果当前不持有股票(
- 更新
last_price
为当前价格。
- 如果当前价格小于上一次的价格(降价):
-
遍历结束后,如果仍持有股票(
state
为 1),则以最后一个价格卖出,计算利润并更新money
。 -
返回总利润
money
。
这个策略的核心思想是:在价格下降时卖出,在价格上升时买入,以期获得最大利润。
运行结果如下所示(仅供参考):
文章来源:https://www.toymoban.com/news/detail-859460.html
4. 总结
这个问题考察了对数组遍历和简单逻辑判断的应用,以及如何从实际问题中抽象出有效的解决方案。通过这种问题,可以加强对简单贪心算法的理解和应用。文章来源地址https://www.toymoban.com/news/detail-859460.html
到了这里,关于代码训练LeetCode(15)买卖股票的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!