字节&leetcode122：买卖股票的最佳时机 II #97

Activity

1. sisterAn

   added

   腾讯

   LeetCode

   字节

   on Aug 19, 2020
2. sisterAn commented on Aug 19, 2020

   

   sisterAn

   on Aug 19, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   解法一：峰底买入，峰顶卖出

   

   如图，在第二天买入，第三天卖出，第四天买入，第五天卖出获利最高，此处代码不再赘述，可以自己尝试写一下

   解法二：贪心算法

   贪心算法，故名思义，总是做出当前的最优选择，即期望通过局部的最优选择获得整体的最优选择。

   某种意义上说，贪心算法是很贪婪、很目光短浅的，它不从整体考虑，仅仅只关注当前的最大利益，所以说它做出的选择仅仅是某种意义上的局部最优，但是贪心算法在很多问题上还是能够拿到最优解或较优解，所以它的存在还是有意义的。

   对应于该题，第一天买入，第二天卖出，…，第 i 天买入，第 i+1 天卖出，如果 i 天买入第 i+1 天卖出有利润则买入，否则不买

   第 i-1 天买入第 i 天卖出获利 prices[i+1]-prices[i] ，我们仅仅需要将 prices[i+1]-prices[i] 的所有正值加起来就是可获取的最大利益

   代码实现：

   let maxProfit = function(prices) {
       let profit = 0
       for (let i = 0; i < prices.length - 1; i++) {
           if (prices[i + 1] > prices[i]) {
               profit += prices[i + 1] - prices[i]
           }
       }
       return profit
   }

   复杂度分析：

   • 时间复杂度：O(n)
   • 空间复杂度：O(1)

   leetcode

   👍React with 👍1Reacted by Jet
3. suixue-FE commented on Aug 20, 2020

   

   suixue-FE

   on Aug 20, 2020

   Last edited by sisterAn

   More actions

   var maxProfit = function(prices) {
     let nums = 0
     if (prices.length>0) {
       let now = prices[0]
       prices.forEach(value=>{
         if (value>now){
           nums+= value - now 
         }
         now = value
       })
     }
     return nums
   }
4. Jet12138 commented on Sep 14, 2022

   

   Jet12138

   on Sep 14, 2022

   More actions

   var maxProfit = function(prices) {
   
       let res = 0;
       let bottom = prices[0];
       for(let i = 1; i<prices.length; i++){
           if(prices[i]>prices[i-1]){
               res = res + prices[i]-bottom;
               bottom = prices[i];
           }else if(prices[i]<=prices[i-1]){
               bottom = prices[i];
           }
       }
   
       return res;
   };