LeetCode买股票系列

问题1:一次交易

原题:Best Time to Buy and Sell Stock

题意:给定一个数组,第 $i$ 个元素表示第 $i$ 天股票的价值,你只能进行一次交易(买入+卖出= 一次交易),请告诉我你获得的最大价值是多少?

Example 1:

1
2
3
4
Input: [7, 1, 5, 3, 6, 4]
Output: 5

1买进,6卖出,获利5

Example 2:

1
2
3
4
Input: [7, 6, 4, 3, 1]
Output: 0

什么时候买都会亏,所以获利0

作为该系列的开门见山题,难度口算,下面说2个可能想到的错误思路:

  • 也许你会觉得,找出最大值和最小值,两者差值就是答案
  • 也许你会觉得,找出最大值和最小值,并且最小值索引小于最大值的索引就行了

对于第一个思路,Example 2: 已经告诉你是错的。

对于第二个思路,你怎么确保最小值索引是小于最大值索引的,万一不是呢,那是不是要进行搜索了呢?那搜索策略又是什么呢?顿时觉得前途一片昏暗

DP

从下至上的计算,设

  • 总天数为n
  • $a[i]$ 是第 $i$ 天的股票价值 $ i = 1,2,…,n$
  • $d[i]$ 是第 $i$ 天买入股票所能达到的最大利益 $ i = 1,2,…,n$

那么 $d[i] = max(a[i], a[i+1], .. , a[n]) - a[i] , i = 1,2,…,n$

那么最大价值就是 $max ( d[1], d[2], .., d[n]), i = 1,2,…,n$

相信聪明的你已经知道代码怎么写了。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
max_after = 0
max_profit = 0
for i in range(len(prices) - 1, -1 , -1):
max_profit = max(max_profit, max(0, max_after - prices[i]))
max_after = max(max_after, prices[i])
return max_profit

贪心

从上至下计算。假设你现在就是一个股民,用变量money表示你现在有多少钱,所以初始你是0元,

  • 买入一个a元的股票,$money = -a$(欠钱)
  • 今天股票价值是b,如果今天卖掉,则 $money = money + b$

要达到两个最大即可,一是买入欠钱最少,所以-a越大越好,二是money越大越好

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
debt = -2147483648
money = 0
for price in prices:
money = max(money, price + debt)
debt = max(debt, -price)
return money

问题2:任意次交易

原题:Best Time to Buy and Sell Stock II

题意:在问题1基础上,交易次数变为任意多次

一瞬间没啥思路,感觉问题很复杂?其实,如果你炒股你就知道,其实很简单,一句话:低买高卖

啥意思?借一张leecode某个答主的图,股票的波动一般像下图一样

低买高卖 是人类的直觉,即在valley(低谷)买入,在peak(顶峰)卖出,这样的收益会比较大。

我们可以分2类情况来讨论,一只股票其实就是下面两种情况的循环往复

股票一直跌,跌倒谷底了,马上要开始涨了

这时候赶紧买啊!因为这个时候买肯定赚,对应的是低谷

  • 如果在valley右侧买,肯定没有valley的收益大
  • 如果在valley左侧买,也没有valley的收益大
  • 如果在顶峰之后再买,那就白白错过了这次稳赚的机会,最后总收益肯定不是最大的

所以结论是必须在低谷买

股票一直涨,涨到顶峰了,马上要开始降了

这时候赶紧抛啊!!因为这一点的收益是最大的,往后的收益肯定没现在这个大,对应的是顶峰

  • 如果在peak左边卖,收益没有peak大
  • 如果在peak右边卖,收益也没有peak大
  • 如果在peak右边的低谷之后再卖,又白白错过了稳赚的机会,最后总收益肯定不是最大

所以结论是必须在顶峰卖

两个顶峰,分开买

第一张图很好的诠释了 $ A + B >= C$ 这一不等式,一看就懂

实现

找一个低谷点买入,在遇到下一个顶峰点的时候立马卖出,这样你就能拿到最大的收益。

不过在代码上要注意最后一天的处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
buy = -1;
profit = 0
for i in range(len(prices)):
if i + 1 >= len(prices):
profit += prices[i] - buy if buy != -1 else 0
elif prices[i + 1] > prices[i]:
buy = prices[i] if buy == -1 else buy
elif prices[i + 1] < prices[i]:
profit += prices[i] - buy if buy != -1 else 0
buy = -1
return profit

优化

其实仔细看刚刚写的代码你会发现,只要是“上升期”的股票我们都可以买,所以代码可以优化为

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
max_profit = 0
for i in range(len(prices) - 1):
max_profit += max(0, prices[i + 1] - prices[i])
return max_profit

问题3:最多两次交易

原题:Best Time to Buy and Sell Stock III

题意:在问题1的基础上,交易次数变为最多两次

这和问题1非常类似,意思是在问题1交易完成后,还能再交易1次。站在问题1的基础上,我们把解法扩展一下。

问题1的的贪心解法的成功运用,表示问题1其实是具有局部最优性质的,意思是这个算法可以用于任何一个局部,当这个局部扩大到全局的时候,就得到的原问题的最优解。那如果把交易次数增加到2次,这种局部最优性质是否还有呢,答案是有的。

我们可以设两对个变量,一对记录第一次交易状态,一对记录第二次交易状态,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
debt1, money1, debt2, money2 = -2147483648, 0, -2147483648, 0
for price in prices:
money2 = max(money2, debt2 + price)
debt2 = max(debt2 , money1 - price)
money1 = max(money1, debt1 + price)
debt1 = max(debt1 , -price)
return money2

问题4:最多K次交易

原题:Best Time to Buy and Sell Stock IV

题意:在问题1的基础上,交易次数变为最多K次,K是程序的输入

注意到K是可变的,所以:

  • K = 1时,退化成问题1
  • K = 2时,退化成问题3
  • K >= 总天数/2 时,退化成问题2

对于第3种情况,我们直接调用问题2的解法即可,以免超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
def maxProfit(self, k, prices):
"""
:type k: int
:type prices: List[int]
:rtype: int
"""
if k >= len(prices) / 2:
return maxProfitAny(prices)

debt, money, max_money = [-2147483648 for i in range(k)], [0 for i in range(k)], 0
for price in prices:
for t in range(k - 1, - 1, -1):
money[t] = max(money[t], debt[t] + price)
debt[t] = max(debt[t], (money[t - 1] if t > 0 else 0) - price)
max_money = max(max_money, money[t])
return max_money

def maxProfitAny(prices):
max_profit = 0
for i in range(len(prices) - 1):
max_profit += max(0, prices[i + 1] - prices[i])
return max_profit
坚持原创文章分享,您的支持将鼓励我继续创作!