股票动态规划团灭
121. 买卖股票的最佳时机
class Solution:
def maxProfit(self, prices: List[int]) -> int:
### 股票状态机
n = len(prices)
if n < 2:
return 0
cash, hold = 0, -prices[0]
#第一天(price[0]) ，不持有时利润cash:为0( 当天没有买股票，或者之前有股票就卖出)，
#持有时利润hold为-price[0] ( 当前购买了price[i], 利润减去price[i])
for i in range(1, n):
cash = max(cash, hold + prices[i])
#不交易继续保持cash,或在卖掉之前hold的股票得到利润prices[i]
hold = max(hold, - prices[i])
#不交易继续保持hold(等待之后某次卖出), 或在今天开始买股票(在此之前无交易，因为本题只允许交易一次)，得到利润 - prices[i]
return cash #要完成交易，最后肯定要卖出股票，所以需要知道cash下的最大利润
### 向前遍历时不断更新最小值和最大差值
if not prices:
return 0
min_cash, max_profit = prices[0], 0
for i in range(1, len(prices)):
min_cash=min(min_cash, prices[i])#判断当前值是不是目前最小值
max_profit=max(max_profit, prices[i]-min_cash)#判断当前值和最小值之间的差值是不是目前最大差值
return max_profit
### dp解法
n=len(prices)
if n<=1:
return 0
else:
dp=[0 for _ in range(n)] #位置i与其左边元素的最大差值（price[i]-price[j], j<i)
dp[0]=0
# dp[1]=dp[1]-dp[0] if dp[1]-dp[0]>0 else 0
for i in range(1, n):
dp[i]=max(0, prices[i]-prices[i-1]+dp[i-1])
return max(dp)
### 优化dp
# n=len(prices)
# if n<=1:
# return 0
# else:
# max_res=0 #存放最高收益
# temp=0 #存放dp[i-1]的结果，因为dp[i]只与dp[i-1]有关
# for i in range(1, n):
# temp=max(0, prices[i]-prices[i-1]+temp)
# #每次计算卖出当前股票的最高收益，当前股票最高收益等于前一天股票最高收益加上当前股票与前一天股票的差价（如果负增长后小于零记为0）
# max_res=max(temp, max_res)
# return max_res
122. 买卖股票的最佳时机 II
class Solution:
### 感觉股票问题的关键在于：先算出相邻两天的差价，然后再在上面做文章
### 因为由微积分(牛顿莱布尼兹公式)可知： eg: p5-p2 = (p5-p4)+(p4-p3)+(p3-p2)
def maxProfit(self, prices: List[int]) -> int:
# return sum(b - a for a, b in zip(prices, prices[1:]) if b > a)
n = len(prices)
if n < 2:
return 0
cash, hold = 0, -prices[0]
for i in range(1, n):
cash = max(cash, hold + prices[i]) ### 当前卖出（利润还要去掉手续费） -> 状态变为不持有cash
hold = max(hold, cash - prices[i]) ### 当前买入 -> 状态变为持有 hold
return cash
max_pro=0
n=len(prices)
if n>1:
for i in range(n-1):
t=prices[i+1]-prices[i]
if t>0: ###只要把相邻两个的大于0的差价累加即可
max_pro+=t
return max_pro
n = len(prices)
if n < 2:
return 0
ans = 0
#记录着低谷
valley = prices[0]
for i in range(1, n):
#发现更低的谷，弃前谷
if prices[i] < valley:
valley = prices[i]
# 发现一个峰比谷高
elif prices[i] > valley:
#累积差
ans += prices[i]-valley
#此峰当作新谷
valley = prices[i]
return ans
123. 买卖股票的最佳时机 III
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) < 2:
return 0
###下面的起始转态是第2天的前一天的（第 1 天)
dp_1_cash, dp_1_hold = 0, -prices[0] #最多交易一次时，前一天为（不持有， 持有）状态时的利润
dp_2_cash, dp_2_hold = 0, -prices[0] #最多交易两次时，前一天为（不持有， 持有）状态时的利润
for price in prices[1:]: #从第2天开始遍历
dp_2_cash = max(dp_2_cash, dp_2_hold + price)
dp_2_hold = max(dp_2_hold, dp_1_cash - price)
dp_1_cash = max(dp_1_cash, dp_1_hold + price)
dp_1_hold = max(dp_1_hold, -price)
return dp_2_cash
188. 买卖股票的最佳时机 IV
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if not prices or not k:
return 0
n = len(prices)
# 当k大于数组长度的一半时，等同于不限次数交易即122题，用贪心算法解决，否则LeetCode会超时，也可以直接把超大的k替换为数组的一半，就不用写额外的贪心算法函数
if k > n//2:
return self.greedy(prices)
dp, res = [[[0]*2 for _ in range(k+1)] for _ in range(n)], []
# dp[i][k][0]表示第i天已交易k次时不持有股票 dp[i][k][1]表示第i天已交易k次时持有股票
# 设定在卖出时加1次交易次数
for i in range(k+1):
dp[0][i][0], dp[0][i][1] = 0, - prices[0]
for i in range(1, n):
for j in range(k+1):
if not j:
dp[i][j][0] = dp[i-1][j][0]
else:
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1] + prices[i])
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0] - prices[i])
# 「所有交易次数最后一天不持有股票」的集合的最大值即为问题的解
for m in range(k+1):
res.append(dp[n-1][m][0])
return max(res)
# 处理k过大导致超时的问题，用贪心解决
def greedy(self, prices):
res = 0
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
res += prices[i] - prices[i-1]
return res
309. 最佳买卖股票时机含冷冻期
'''
每天可能存在三种状态：
hold：继续持有股票
sold：卖出股票
rest：什么都不做
(冷冻期为1天: 卖出股票后, 无法在第二天买入股票) 转换关系如下：
hold： 可由两个情况转换来
前一天hold，当日rest
前一天rest，当日买入股票变为hold
sold：
前一天hold，当日卖出股票
rest：
前一天sold，当日必须rest
前一天rest，当日继续rest
所以
sold[i] = hold[i-1] + price[i];
hold[i] = max(hold[i-1], rest[i-1] - price[i])
rest[i] = max(rest[i-1], sold[i-1])
最后一天最大值情况为要么什么都不做，要么卖出股票，即 max(sold，rest)
'''
# @lc code=start
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n < 2:
return 0
cash, hold = 0, -prices[0] # 代表昨天状态为cash和hold时的“利润”，第一天如果持有的话，那就是当天买了，花掉prices[0]，利润为-prices[0]
dp_pre_0=0 #代表dp[i-2][cash] #“前天”为cash状态下的利润
for i in range(1, n):
temp=cash
#昨天cash今天rest(无操作)， 昨天hold,今天卖出，利润+prices[i]
cash = max(cash, hold + prices[i]) # max()中的 cash和hold 都是指前一天的状态， 等号前的算的才是当前的状态
#昨天hold今天rest(无操作)， “前天”cash,今天买入（昨天必须无操作，那就从前天的cash状态（可能是前天rest或卖出）转移过来），利润-prices[i]
hold = max(hold, dp_pre_0 - prices[i]) #每次 sell 之后要等一天才能继续交易,第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1
dp_pre_0=temp #i-1天/昨天cash状态下的利润，就变成明天的“前天”为cash状态下的利润
return cash
714. 买卖股票的最佳时机含手续费
class Solution:
### 一个买入卖出操作对只收一次手续费fee，可以认为卖出的时候要收fee(在利润里扣除)
def maxProfit(self, prices: List[int], fee: int) -> int:
cash, hold = 0, -prices[0]
for i in range(1, len(prices)):
cash = max(cash, hold + prices[i] - fee) ### 当前卖出（利润还要去掉手续费） -> 状态变为不持有cash
hold = max(hold, cash - prices[i]) ### 当前买入 -> 状态变为持有 hold
return cash
### 在122基础上修改
n = len(prices)
if n < 2:
return 0
ans = 0
#记录着低谷
valley = prices[0]
for i in range(1, n):
#发现更低的谷，弃前谷
if prices[i] < valley:
valley = prices[i]
# prices[i]-fee：扣掉手续费的峰
# 发现一个扣掉手续费的峰比谷高
elif prices[i]-fee > valley:
#累积差
ans += (prices[i]-fee)-valley
#此扣掉手续费的峰当作新谷
valley = prices[i]-fee
return ans
901. 股票价格跨度
class StockSpanner:
def __init__(self):
self.stack=[]
############################ 有点难理解 ##############################
def next(self, price: int) -> int:
### 单调栈解法
w=1 #每个price的 w 初始化为1（自身， 前面没有比它小的元素）
#维护一个栈内元素从左到右单调递减的栈，每个price的 w 值相当于同时维护着一个结果列表
while self.stack and price >= self.stack[-1][0]:
w+=self.stack.pop()[1]
#每弹出一个元素，当前的W就要加上这个弹出元素的w,相当于当前栈内比price小的元素的w的值累加，
#假设当前栈内比price小的元素有【p1, p2】(栈内元素从左到右单调递减)，所以p1>p2, 且p1的w值和p2的w值并无重叠，
#因为p2的w值是计算的 p1到p2之间（都比p2小）的元素的个数
self.stack.append((price, w))
return w
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)
