刷题笔记:力扣第122题-买卖股票的最佳时机Ⅱ

1.为了利益最大化，将股票的每日价格看成一个折线图，在低点买入高位卖出就一定能赚钱，实际上就是寻找数组的极值点。使用贪心算法，完整代码如下：

1. int maxProfit(int* prices, int pricesSize) { 2. // 只有一天股价，无法完成买卖，利润为0 3. if (pricesSize == 1) return 0; 4. 5. // res 累计总利润 6. int res = 0; 7. // buy 记录买入价格，-1代表当前无持仓 8. int buy = -1; 9. // 从第二天股价开始遍历 10. for (int i = 1; i < pricesSize; i++){ 11. // 当前无持仓，且当天股价高于前一天，在前一天买入 12. if (buy == -1 && prices[i] > prices[i - 1]){ 13. buy = prices[i - 1]; 14. } 15. // 当前持有股票 16. if (buy >= 0){ 17. // 当天股价低于前一天，前一天卖出，结算利润，清空持仓 18. if (prices[i] < prices[i - 1]){ 19. res += prices[i - 1] - buy; 20. buy = -1; 21. } else if (i == pricesSize - 1){ 22. // 遍历到最后一天仍持有股票，当天卖出结算利润 23. res += prices[i] - buy; 24. buy = -1; 25. } 26. } 27. } 28. 29. return res; 30. }

该算法时间复杂度为O(n)，空间复杂度为O(1)。

2.官方的贪心算法代码写的极其简单，如果第二天比第一天的股票价格贵就买入并卖出。因为题目上强调了可以当天同时买入与卖出，行为上复杂化且等价于寻找波峰波谷，但代码就会变得非常简单：

1. int maxProfit(int* prices, int pricesSize) { 2. // res 存放累计的最大利润 3. int res = 0; 4. // 只有一天价格，无法进行买卖，利润为0 5. if (pricesSize == 1) return 0; 6. // 从第二天开始遍历所有价格 7. for (int i = 1; i < pricesSize; i++){ 8. // 相邻两天差价为正就累加利润，差价为0或负数不加 9. res += fmax(0, prices[i] - prices[i - 1]); 10. } 11. 12. return res; 13. }

3.官方答案还有动态规划算法，看起来比贪心算法要复杂，当下就不再尝试了。