LeetCode买股票系列

编程题

发布日期: 2017-11-11

问题1：一次交易

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

Example 1:

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

1买进，6卖出，获利5

Example 2:

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$

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

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越大越好

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$ 这一不等式，一看就懂

实现

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

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

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

优化

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

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次，这种局部最优性质是否还有呢，答案是有的。

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

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的解法即可，以免超时

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