代码随想录算法训练营第四十天 | leetcode：买卖股票的最佳时机,买卖股票的最佳时机II
19 / 0 / 创建于 4个月前
_zzh 的个人博客
121. 买卖股票的最佳时机
解题方法
思路：与打家劫舍三类似，dp数组需要记录两个状态，持有股票状态与不持有股票状态，还需要记录天数，所以dp需要使用二维数值。
- dp数组的含义：其中 “持有/不持有” 状态不特指当天 “持有/不持有”，可能是今天之前 “买入/卖出” 到第i天的时候还保持 “持有/不持有” 状态
- dp[i][0]：第i天时，持有股票的状态,
- dp[i][1]：第i天时，不持有股票的状态
- 确定递推公式：假设初始状态利润为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]表示卖出获得的利润
- 初始化dp数组：dp[0][0]表示第0天持有，买入股票，此时利润为0 - prices[0]; dp[0][1] 表示第0天未持有，未买入股票，所以不产生利润，初始化为0；即：dp[0][0] = -prices[0]； dp[0][1] = 0；
- 遍历顺序：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的不同。
- dp数组的含义：其中 “持有/不持有” 状态不特指当天 “持有/不持有”，可能是今天之前 “买入/卖出” 到第i天的时候还保持 “持有/不持有” 状态
- dp[i][0]：第i天时，持有股票的状态,
- dp[i][1]：第i天时，不持有股票的状态
- 确定递推公式：假设初始状态利润为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]表示卖出获得的利润
- 初始化dp数组：dp[0][0]表示第0天持有，买入股票，此时利润为0 - prices[0]; dp[0][1] 表示第0天未持有，未买入股票，所以不产生利润，初始化为0；即：dp[0][0] = -prices[0]； dp[0][1] = 0；
- 遍历顺序：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 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：