LeetCode 股票系列（一）

今天我们来聊聊 Leetcode 的华尔街之狼（The Wolf of Wall Street）系列，也称股票系列， 在 Leetcode 上有 6 题之多。

本文会通过讲解其中的几道经典题目再次探究动态规划的魅力，希望能帮助大家对 DP 有更深入的理解。

这类题目在面试中非常常见，也有很多的变种，比如我就被问过不止要返回 profit，还要返回在哪天交易。

不过万变不离其宗，把握住买卖的原则，你就是赢家。

1. Best Time to Buy and Sell Stock

给你一组数组 prices=[7,1,5,3,6,4]。prices[i] 代表在第i天股票的价格。你可以进行买与卖的操作，但你得先买了才能卖。（也就是不能 short）你最多进行一次买与卖的操作，问你能够赚到的最大收益是多少？从本题的数据例子来看，我们如果在 i=1 天买和在 i=4天卖，我们能够赚到 p[4]-p[1]=5 的收益。这是我们能够做到的最大收益，其它的操作都不能赚的比5多。

问题分析 ：

首先如果我们在第 i 天进行买的操作，那么卖的操作一定得发生在第 i 天之后，也就是 prices[i+1 : n] 里

• 以 prices=[7,1,5,3,6,4] 作为例子，如果我们在 prices[0] 买，那么卖一定发生在 prices[1 : 5]。
  
• 同理，如果我们在 prices[1] 买，卖一定发生在 prices[2 : 5]。
  我们可以把所有的 （买，卖）  pair 生成出来然后找到收益性最高的那对即可。
  

方法1 ：暴力枚举

public int maxProfit(int[] prices) {
        int maxProfit = 0; //我们可以不进行操作，所以初始是 0 而不是 INT_MIN
        for(int i = 0; i < prices.length; i++){
            //在 i 天 进行购买
            for(int j = i + 1; j < prices.length; j++){
                //在 j 天进行出售
                int profit = prices[j] - prices[i];
                maxProfit = Math.max(maxProfit, profit);
            }
        }
        return maxProfit;
    }

代码总结：

• 我们枚举所有的 (i, j) pair，i 代表买，j 代表卖，并且 i < j，但以上暴力代码的时间复杂度是 O(n^2)，我们可不可以做的更好呢？

时空复杂度：

• 时间复杂度：O(N^2)
• 空间复杂度：O(1)

方法2：

• 如果我们在第 i 天进行买的操作，那么卖的操作一定还是得发生在 prices[i+1 : n] 这个定理是不变的。
• 换句话说，对于每个买的操作，prices[i]，我们只需要找到 prices[i+1 : n] 里最大的数即可。
• 我们可以用一个dp array 去记录，dp[i] 表示 max(prices[i : n]) 。
• 如果我们在 i 这天进行买的操作，获得的最大的收益就是 dp[i+1] - prices[i] (这里我们要注意outbound)

public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int n = prices.length;
        int dp[] = new int[n]; 
        dp[n - 1] = prices[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            dp[i] = Math.max(prices[i], dp[i + 1]);
        }
        for (int i = 0; i < n - 1; i++) {
            maxProfit = Math.max(maxProfit, dp[i + 1] - prices[i]);
        }
        return maxProfit;
    }

时空复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(N)

方法3：

我们其实可以把空间压缩到 O(1)，比起使用一个dp array 去记录，我们可以直接一边走一边记录。

public int maxProfit(int[] prices) {
        int n = prices.length;
        int maxSell = prices[n - 1];
        int maxProfit = 0;
        for (int i = n - 2; i >= 0; i--) {
            maxProfit = Math.max(maxProfit, maxSell - prices[i]);
            maxSell = Math.max(maxSell, prices[i]);
        }
        return maxProfit;
    }

时空复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(1)