采用“贪心”策略，实现买股票只赢不亏~~~

大家好，我是「程序员小熊」。今天给大家带来一道与「贪心算法」相关的题目，这道题同时也是字节、苹果和亚马逊等互联网大厂的面试题，即力扣上的第 122 题-买卖股票的最佳时机 II。

本文主要介绍「贪心」的策略来解答此题，供大家参考，希望对大家有所帮助。

 

 

贪心算法是通过做出一系列选择来求出问题的最优解，在每个决策点，它做出当时看来最佳的选择。通过「局部最优」的选择，寄希望实现「全局最优解」。

「举例」

以 prices = [1,4,2,3,7] 为例子，求获得的最大利润，如下图示。

例子

 

遍历数组 prices，第一天一定买入；

第一次决策

 

尔后判断判断第二天的价格是否大于第一天，大于则卖出（局部最优）；

价格递增时决策

 

卖出后，如果后面一天的价格小于当天的价格，则当天不买，防止亏本；

价格递减时决策

 

以此类推，其采用贪心策略买卖股票的完整决策过程如下动图示

决策的整个过程

「C」

  1. 1 int maxProfit(int* prices, int pricesSize){
  2. 2     int ans = 0;
  3. 3     for (int i = 1; i < pricesSize; ++i) {
  4. 4         /* 后一天的价格比前一天高，则卖出（当前最佳策略） */
  5. 5         ans += fmax(0, prices[i] - prices[i - 1]);
  6. 6     }
  7. 7 
  8. 8     return ans;
  9. 9 }

View Code

 

「C++」

  1. 1 int maxProfit(vector<int>& prices) {
  2. 2     int ans = 0;
  3. 3     for (int i = 1; i < prices.size(); ++i) {
  4. 4         ans += max(0, prices[i] - prices[i - 1]);
  5. 5     }
  6. 6 
  7. 7     return ans;
  8. 8 }

View Code

 

「Java」

  1. 1 int maxProfit(int[] prices) {
  2. 2     int ans = 0;
  3. 3     for (int i = 1; i < prices.length; ++i) {
  4. 4         ans += Math.max(0, prices[i] - prices[i - 1]);
  5. 5     }
  6. 6 
  7. 7     return ans;
  8. 8 }

View Code

 

「Python3」

  1. 1 def maxProfit(self, prices: List[int]) -> int:
  2. 2     ans = 0
  3. 3     for i in range(1, len(prices)):
  4. 4         ans += max(0, prices[i] - prices[i - 1])
  5. 5     
  6. 6     return ans

View Code

 

「Golang」

  1.  1 func maxProfit(prices []int) int {
  2.  2     ans := 0
  3.  3     for i := 1; i < len(prices); i++ {
  4.  4         profit := prices[i] - prices[i-1]
  5.  5         if profit > 0 {
  6.  6           ans += profit
  7.  7         }        
  8.  8     } 
  9.  9     
  10. 10     return ans   
  11. 11 }

View Code

 

「复杂度分析」

时间复杂度：「O(n)」，其中 n 是数组的长度，需要遍历一遍数组。

空间复杂度：「O(1)」，未开辟额外的空间。

版权声明：本文为Dine原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/Dine/p/128yt.html