122.买卖股票的最佳时机II
image.png

我的思路

妈耶没想到我做出来了。用的是之前那个376. 摆动序列-波峰波谷的思想，只在波谷买入，波峰卖出。
坑就是，这样的for循环没有判断最后一个，我要单独判断最后一天的买卖。
【但AC了就很开心哈哈= =】

  1. var maxProfit = function(prices) {
  2.     let preDiff =0;
  3.     let curDiff =0;
  4.     let owned =false;
  5.     let result =0;
  6.     let buyin =0;
  7.     let soldout =0;
  10.     for(let i =0;i<prices.length-1;i++){
  11.         //是波谷且owned为false才买入
  12.         curDiff =prices[i+1]-prices[i];
  13.         if(!owned &&(preDiff<=0&&curDiff>0)){
  14.             buyin =prices[i];
  15.             owned =!owned;
  16.         }
  17.         //是波峰且owned为true才卖出
  18.         else if(owned &&(preDiff>=0&&curDiff<0)){
  19.             soldout =prices[i];
  20.             result+= soldout-buyin;
  21.             owned =!owned;
  23.         }
  24.         console.log(buyin);
  25.         console.log(soldout);
  26.         preDiff =curDiff;
  27.     }
  29.     if(owned){
  30.         //最后还持有，卖出
  31.         let finalResult =prices[prices.length-1] -buyin;
  32.         if(finalResult>=0){
  33.             return result+finalResult;
  34.         }else{
  35.             return result;
  36.         }
  37.     }
  38.     return result;
  40. };
  • 时间复杂度：$O(n)$

  • 空间复杂度：$O(1)$

    大佬思路

    分解利润！
    假如第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]。
    相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
    局部最优：收集每天的正利润，全局最优：求得最大利润。

  • 时间复杂度：$O(n)$

  • 空间复杂度：$O(1)$

呜呜呜大佬好聪明啊。代码好短
image.png

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

动态规划

还能动态规划做，见动态规划分组下的解答