https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
solution
Copy # 一次迭代过程,只记录之前出现的最低值,也计算目前出现的最大利润。两种计算非同时触发
class Solution :
def maxProfit ( self , prices : List [ int ] ) -> int :
low = float ( 'inf' )
profit = 0
for price in prices :
if price < low : # 可转化为 low = min(low, i), 截止到目前遇到的最低价格
low = price
if price - low > profit : # 可转化为 profit = max(profit, i - low), 截止目前的最大利润
profit = price - low
return profit
时间复杂度:O(n)
空间复杂度:O(1)
动态规划
dp含义很关键,注意dp[i][0]和dp[i][1]分布是持有 和不持有 股票,手里最多现金。持有可以是原来就持有,也可以是当天才买。不持有可以是一直不持有,可以是当天才卖。
初始可以认为现金是0,可以初始假设了某笔钱,最后也需要减掉。然后,中间如果有亏损,本身也是负的现金
Copy # 只和过去一个时间有关的, 空间可以优化
class Solution :
def maxProfit ( self , prices : List [ int ] ) -> int :
dp = [[ 0 ] * 2 for _ in range ( len (prices)) ]
dp [ 0 ] [ 0 ] = - prices [ 0 ]
dp [ 0 ] [ 1 ] = 0
for i in range ( 1 , len (prices)):
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 [ - 1 ] [ 1 ]
时间复杂度:O(n)
空间复杂度:O(n)
follow up-股票买卖类
122. Best Time to Buy and Sell Stock II
Copy class Solution :
def maxProfit ( self , prices : List [ int ] ) -> int :
dp = [[ 0 ] * 2 for _ in range ( len (prices)) ]
dp [ 0 ] [ 0 ] = - prices [ 0 ]
dp [ 0 ] [ 1 ] = 0
for i in range ( 1 , len (prices)):
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 [ - 1 ] [ 1 ]
时间复杂度:O(n)
空间复杂度:O(n)
Copy class Solution :
def maxProfit ( self , prices : List [ int ] ) -> int :
if not prices :
return 0
res = 0
for i in range ( 1 , len (prices)):
if prices [ i ] >= prices [ i - 1 ]: # 递增区间
res = res + prices [ i ] - prices [ i - 1 ] # 和
else :
continue
return res
123. Best Time to Buy and Sell Stock III
dp含义差不多?类似问题中,二维dp中的第二维是某种状态枚举
Copy class Solution :
def maxProfit ( self , prices : List [ int ] ) -> int :
if len (prices) <= 1 :
return 0
dp = [[ 0 ] * 4 for _ in range ( len (prices)) ]
dp [ 0 ] [ 0 ] = - prices [ 0 ]
dp [ 0 ] [ 2 ] = - prices [ 0 ] # 注意第二次持有的初始化
for i in range ( 1 , len (prices)):
dp [ i ] [ 0 ] = max (dp[i - 1 ][ 0 ], - prices[i]) # 注意和前几天的比较
dp [ i ] [ 1 ] = max (dp[i - 1 ][ 1 ], dp[i - 1 ][ 0 ] + prices[i])
dp [ i ] [ 2 ] = max (dp[i - 1 ][ 2 ], dp[i - 1 ][ 1 ] - prices[i])
dp [ i ] [ 3 ] = max (dp[i - 1 ][ 3 ], dp[i - 1 ][ 2 ] + prices[i])
return max (dp[ - 1 ][ 1 ], dp[ - 1 ][ 3 ])
时间复杂度:O(n)
空间复杂度:O(n), 可继续优化至O(1)
188. Best Time to Buy and Sell Stock IV
Copy class Solution :
def maxProfit ( self , k : int , prices : List [ int ] ) -> int :
if len (prices) <= 1 :
return 0
dp = [[ 0 ] * ( 2 * k + 1 ) for _ in range ( len (prices)) ]
for j in range ( 1 , 2 * k, 2 ):
dp [ 0 ] [j] = - prices [ 0 ] # 同样注意所有奇数次持有的初始化
for i in range ( 1 , len (prices)):
for j in range ( 0 , 2 * k - 1 , 2 ):
dp [ i ] [j + 1 ] = max (dp[i - 1 ][j + 1 ], dp[i - 1 ][j] - prices[i])
dp [ i ] [j + 2 ] = max (dp[i - 1 ][j + 2 ], dp[i - 1 ][j + 1 ] + prices[i])
return dp [ - 1 ] [ 2 * k]
时间复杂度:O(n)
空间复杂度:O()
309. Best Time to Buy and Sell Stock with Cooldown
Copy class Solution :
def maxProfit ( self , prices : List [ int ] ) -> int :
if len (prices) <= 1 :
return 0
dp = [[ 0 ] * 4 for _ in range ( len (prices)) ]
dp [ 0 ] [ 0 ] = - prices [ 0 ]
for i in range ( 1 , len (prices)):
dp [ i ] [ 0 ] = max (dp[i - 1 ][ 0 ], dp[i - 1 ][ 2 ] - prices[i]) # hold, 之前持有或非冷冻期买入
dp [ i ] [ 1 ] = dp [ i - 1 ] [ 0 ] + prices [ i ] # sell, 前一天持有后卖出,卖出后进入的是冷冻状态,因此没有dp[i-1][1]
dp [ i ] [ 2 ] = max (dp[i - 1 ][ 2 ], dp[i - 1 ][ 1 ]) # cool, 注意该状态是冷冻或冷冻期之后可买入的状态, 因此还要和自己过去比较
return max (dp[ - 1 ][ 1 ], dp[ - 1 ][ 2 ])
时间复杂度:O(n)
空间复杂度:O()
714. Best Time to Buy and Sell Stock with Transaction Fee
Copy class Solution :
def maxProfit ( self , prices : List [ int ], fee : int ) -> int :
if len (prices) <= 1 :
return 0
dp = [[ 0 ] * 2 for _ in range ( len (prices)) ]
dp [ 0 ] [ 0 ] = - prices [ 0 ]
for i in range ( 1 , len (prices)):
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] - fee)
return dp [ - 1 ] [ 1 ]
时间复杂度:O(n)
空间复杂度:O()