代码随想录算法训练营第四十天 | leetcode:买卖股票的最佳时机,买卖股票的最佳时机II

121. 买卖股票的最佳时机

解题方法

思路:与打家劫舍三类似,dp数组需要记录两个状态,持有股票状态与不持有股票状态,还需要记录天数,所以dp需要使用二维数值。

  1. dp数组的含义:其中 “持有/不持有” 状态不特指当天 “持有/不持有”,可能是今天之前 “买入/卖出” 到第i天的时候还保持 “持有/不持有” 状态
    • dp[i][0]:第i天时,持有股票的状态,
    • dp[i][1]:第i天时,不持有股票的状态
  2. 确定递推公式:假设初始状态利润为0;
    • dp[i][0] = max(dp[i-1][0], 0-prices[i]);
      • dp[i-1][0]:在第i天之前就买入了,在第i天保持持有状态
      • 0-prices[i]:在第i天买入的状态,-prices[i]表示买入的利润,因为只能买入一次,所以第一次买入前,利润肯定是0,买入之后,就变成0-prices。
    • dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
      • dp[i-1][1]:在第i天之前就卖出了,在第i天保持不持有状态
      • dp[i-1][0] + prices[i]:在第i天卖出,dp[i-1][0]表示第i天之前的持有状态,+ prices[i]表示卖出获得的利润
  3. 初始化dp数组:dp[0][0]表示第0天持有,买入股票,此时利润为0 - prices[0]; dp[0][1] 表示第0天未持有,未买入股票,所以不产生利润,初始化为0;即:dp[0][0] = -prices[0]; dp[0][1] = 0;
  4. 遍历顺序:dp[i],依赖与dp[i-1],所以按数组顺序从左到右。

code

动态规划

class Solution {

    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $dp = [];
        //dp[i][0]表示第i天持有股票的状态
        //dp[i][1]表示第i天不持有股票的状态
        $dp[0][0] = -$prices[0];    
        $dp[0][1] = 0;
        $len = count($prices);
        for($i = 1; $i < $len; $i++){
            //昨天就买入了与当天买入的最大值
            $dp[$i][0] = max($dp[$i-1][0], -$prices[$i]);
            //昨天已经卖出与当天卖出的最大值
            $dp[$i][1] = max($dp[$i-1][1], $dp[$i-1][0] + $prices[$i]);
        }
        return $dp[$len - 1][1];
    }
}

复杂度

时间复杂度

O(n),其中 n 为 prices 的长度

空间复杂度

O(n)

贪心

class Solution {

    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $low = PHP_INT_MAX;
        $result = 0;
        for ($i = 0; $i < count($prices); $i++) {
            $low = min($low, $prices[$i]);  // 取最左最小价格
            $result = max($result, $prices[$i] - $low); // 直接取最大区间利润
            //print_r([$low,$result]);
        }
        return $result;
    }
}

复杂度

时间复杂度

O(n),其中 n 为 prices 的长度

空间复杂度

O(1)

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

解题方法

思路:dp数组需要记录两个状态,持有股票状态与不持有股票状态,还需要记录天数,所以dp需要使用二维数值。与买卖股票的最佳时机I基本相同,不同的点在于,买卖股票的最佳时机II可以多次买入卖出,需要表示第i天持有股票状态时,那买入股票前的利润就不一定是0了,因为可能之前的买入卖出操作已存在利润,这就是买卖股票的最佳时机II 与 买卖股票的最佳时机I的不同。

  1. dp数组的含义:其中 “持有/不持有” 状态不特指当天 “持有/不持有”,可能是今天之前 “买入/卖出” 到第i天的时候还保持 “持有/不持有” 状态
    • dp[i][0]:第i天时,持有股票的状态,
    • dp[i][1]:第i天时,不持有股票的状态
  2. 确定递推公式:假设初始状态利润为0;
    • dp[i][0] = max(dp[i-1][0], dp[i-1][0]-prices[i]);
      • dp[i-1][0]:在第i天之前就买入了,在第i天保持持有状态
      • dp[i-1][0]-prices[i]:在第i天买入的状态,-prices[i]表示买入的利润。因为可以买卖多次,所以当前买入不一定是第一次,利润肯定不一定是0,所以这里相比买卖股票的最佳时机I需要变成 dp[i-1][1] 表示第i天买入前,不持有股票的状态。dp[i-1][1] - prices[i]后就能表示当前买入股票的状态。
    • dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
      • dp[i-1][1]:在第i天之前就卖出了,在第i天保持不持有状态
      • dp[i-1][0] + prices[i]:在第i天卖出,dp[i-1][0]表示第i天之前的持有状态,+ prices[i]表示卖出获得的利润
  3. 初始化dp数组:dp[0][0]表示第0天持有,买入股票,此时利润为0 - prices[0]; dp[0][1] 表示第0天未持有,未买入股票,所以不产生利润,初始化为0;即:dp[0][0] = -prices[0]; dp[0][1] = 0;
  4. 遍历顺序:dp[i],依赖与dp[i-1],所以按数组顺序从左到右。

code

动态规划

class Solution {

    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
         $dp = [];
        //dp[i][0]表示第i天持有股票的状态
        //dp[i][1]表示第i天不持有股票的状态
        $dp[0][0] = -$prices[0];
        $dp[0][1] = 0;
        $len = count($prices);
        for($i = 1; $i < $len; $i++){
            //昨天就买入了与当天买入的最大值(因为可以买卖多次,当天买入应该是昨天不持有(卖出)的状态)
            $dp[$i][0] = max($dp[$i - 1][0], $dp[$i - 1][1] - $prices[$i]);
            //昨天已经卖出与当天卖出的最大值
            $dp[$i][1] = max($dp[$i - 1][1], $dp[$i - 1][0] + $prices[$i]);
        }
        return $dp[$len-1][1];
    }
}

复杂度

时间复杂度

O(n)

空间复杂度

O(n)

贪心

class Solution {

    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $count = 0;
        for($i = 1; $i < count($prices); $i++){
            //求利润
            $diff = $prices[$i] - $prices[$i-1];
            //正利润累加
            if($diff > 0){
                $count += $diff;
            }
        }
        return $count;
    }
}

复杂度

时间复杂度

O(n)

空间复杂度

O(1)

本作品采用《CC 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!