代码训练LeetCode(15)买卖股票

代码训练(15)LeetCode之买卖股票

Author: Once Day Date: 2024年4月22日
漫漫长路，才刚刚开始…
全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客
参考文章:

• 122. 买卖股票的最佳时机 II - 力扣（LeetCode）
  
• 力扣 (LeetCode) 举世极客挚爱的技术发展平台
  

  
1. 原题

   给你一个整数数组 prices ，其中 prices 体现某支股票第 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 天的股票价格。规则是在任何一天，可以决定是否购买大概出售股票，但最多只能持有一股股票，并且允许在同一天买入和卖出。标题要求返回可能的最大利润。
关键在于明白在哪些天买入和在哪些天卖出可以获得最大利润。由于可以在同一天买入和卖出，那么只要本日的价格比昨天高，就可以以为昨天买入，本日卖出是有利可图的。
具体计谋是：

• 遍历价格数组，从第二天开始比力。
  
• 每当发现本日的价格比昨天的高，就计算这一天的利润（本日的价格减去昨天的价格），并累加到总利润中。
  

这种计谋的利益在于不需要维护任何复杂的状态，只需要在价格上升的时间“买卖”即可。
分析步调：

• 初始化一个变量 maxProfit 来存储总利润，初值设为0。
  
• 从第二天开始遍历价格数组。
  
• 对于每一天，如果价格比前一天高，就将差价加到 maxProfit 上。
  
• 最后返回 maxProfit。
  

性能优化关键点：

• 执行速度：这个算法的时间复杂度是 O(n)，由于只需要遍历一次价格数组，这黑白常高效的。
  
• 内存使用：空间复杂度为 O(1)，由于我们只使用了常数额外空间。
  

3. 代码实现

1. int maxProfit(int* prices, int pricesSize) {
2.     int32_t i, state, money, buy_price, last_price;
4.     state = 1; /* 买入 */
5.     money = 0;
6.     last_price = buy_price = prices[0];
7.     for (i = 1; i < pricesSize; i++) {
8.         if (prices[i] < last_price) {
9.             /* 降价卖出 */
10.             if (state) {
11.                 money += last_price - buy_price;
12.                 state = 0;
13.             }
14.         } else if (prices[i] > last_price) {
15.             /* 升价买入 */
16.             if (!state) {
17.                 buy_price = last_price;
18.                 state = 1;
19.             }
20.         }
21.         last_price = prices[i];
22.     }
24.     /* 最后直接卖掉 */
25.     if (state) {
26.         money += last_price - buy_price;
27.     }
29.     return money;
30. }

复制代码

这段代码实现了一个简单的股票交易计谋，目的是最大化利润。函数的输入是一个整数数组 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。
  

这个计谋的核心思想是：在价格降落时卖出，在价格上升时买入，以期获得最大利润。
运行结果如下所示(仅供参考):

4. 总结

这个问题观察了对数组遍历和简单逻辑判断的应用，以及如何从实际问题中抽象出有效的解决方案。通过这种问题，可以增强对简单贪婪算法的明白和应用。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。