算法-贪心/动态规划-买卖股票的最佳时机

1 买卖股票的最佳时机 V1

1.1 概述

1.1.1 题目出处

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

1.1.2 题目描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

1.2 双指针

1.2.1 思路

双指针，一个记录最小股票价格，一个记录结果。

1.2.2 代码

class Solution {
    public int maxProfit(int[] prices) {
        int left = Integer.MAX_VALUE;
        int result = 0;
        for(int p : prices){
            if(p < left){
                // 小于左边界，则更新左边界
                left = p;
            } else if(p - left > result){
                // 利润大于已记录的最大利润
                result = Math.max(result, p - left);
            }
        }
        return result;
    }
}

1.2.3 时间复杂度

O(N)

1.2.4 空间复杂度

O(1)

1.3 动态规划 V1

1.3.1 思路

dp[i]表示前i日的最大利润。

则转移方程为：
dp[i] = max( dp[i-1]), prices[i] - min(prices[0 -> i])。

初始：
dp[0] = 0;

返回值：
dp[prices.length - 1]

1.3.2 代码

class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length < 2){
            return 0;
        }
        int[] dp = new int[prices.length];
        dp[0] = 0;
        int min = prices[0];
        for(int i = 1; i < prices.length ; i++){
            dp[i] = Math.max(dp[i - 1], prices[i] - min);
            min = Math.min(min, prices[i]);
        }

        return dp[prices.length - 1];
    }
}

1.3.3 时间复杂度

O(N)

1.3.4 空间复杂度

O(N)

1.4 动态规划 V2

1.4.1 思路

其实我们只需要记录当前最大利润，不需要记录每一天的最大利润。

因为每天的最大利润肯定是不会比前面的小的。

所以只需要一个变量存最大利润即可，不需要dp[n]。

1.4.2 代码

class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        if(prices == null || prices.length < 2){
            return result;
        }

        int min = prices[0];
        for(int i = 1; i < prices.length ; i++){
            result = Math.max(result, prices[i] - min);
            min = Math.min(min, prices[i]);
        }

        return result;
    }
}

1.4.3 时间复杂度

O(N)

1.4.4 空间复杂度

O(1)

2 买卖股票的最佳时机 V2

2.1 概述

2.1.1 题目出处

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

2.1.2 题目描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

2.2 贪心

2.2.1 思路

只要后项大于前项，则累加到结果中。
想象连续两次涨，就累加了两次的差值，其实就等于 第三次卖 - 第一次买的差值

其实是一个trick，没有实际操作性，因为你不可能提前知道连续两天的价格来决定第一天低价格买入第二天高价格卖出。

以下内容转自贪心算法详解，作者 liweiwei1419

因此，

• “贪心算法” 和 “动态规划”、“回溯搜索” 算法一样，完成一件事情，是分步决策的；
• “贪心算法” 在每一步总是做出在当前看来最好的选择，“最好” 的意思往往根据题目而来，可能是 “最小”，也可能是 “最大”；
• 贪心算法和动态规划相比，它既不看前面（也就是说它不需要从前面的状态转移过来），也不看后面（无后效性，后面的选择不会对前面的选择有影响）
  因此贪心算法时间复杂度一般是线性的，空间复杂度是常数级别的。

这道题 “贪心” 的地方在于，对于 “今天的股价 - 昨天的股价”，得到的结果有 3 种可能：

• 正数
• 0
• 负数。

贪心算法的决策是：只累加正数。

2.2.2 代码

class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        if(prices.length < 2){
            return result;
        }

        // 只要后项大于前项，则累加到结果中。
        // 想象连续两次涨，就累加了两次的差值，其实就等于 第三次卖 - 第一次买的差值
        for(int i = 1; i < prices.length; i ++){
            if(prices[i] > prices[i-1]){
                result += (prices[i] - prices[i-1]);
            }
        }
        return result;
    }
}

2.2.3 时间复杂度

O(N)

2.2.4 空间复杂度

O(1)

2.3 动态规划 V1

2.3.1 思路

可用贪心解决的一般也能用动态规划。

• dp[i][0]代表该天不持有股票的最大利润
• dp[i][1] 代表该天持有股票的最大利润

则转移方程为：

dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);

初始：

dp[0][0] = 0;
dp[0][1] = 0 - prices[0];

返回值：

// 因为最后一天必须不能持有股票，否则肯定利润小于dp[prices.length - 1][0]
dp[prices.length - 1][0]

2.3.2 代码

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length < 2){
            return 0;
        }

        // dp[i][0]代表该天不持有股票的最大利润
        // dp[i][1] 代表该天持有股票的最大利润
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = 0 - prices[0];

        for(int i = 1; i < prices.length; i ++){
            // 第二个表示 i-1日持有股票，但在i日卖出
            // 因为这暗含了加上 用 prices[i] 减去 前面买的那只股票的价格的差价
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }
        return dp[prices.length - 1][0];
    }
}

2.3.3 时间复杂度

O(N)

2.3.4 空间复杂度

O(N)

2.4 动态规划 V2

2.4.1 思路

最大利润不会减少，所以也可以用两个变量分别记录拥有和不拥有股票时的最大利润。

这样空间复杂度降为O(N)

2.3.2 代码

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length < 2){
            return 0;
        }

        int haveCost = 0 - prices[0];
        int notHaveCost = 0;

        for(int i = 1; i < prices.length; i ++){
            // 第二个表示 i-1日持有股票，但在i日卖出
            // 因为这暗含了加上 用 prices[i] 减去 前面买的那只股票的价格的差价
            notHaveCost = Math.max(notHaveCost, haveCost + prices[i]);
            haveCost = Math.max(haveCost, notHaveCost - prices[i]);
        }
        return notHaveCost;
    }
}

2.4.3 时间复杂度

O(N)

2.4.4 空间复杂度

O(1)

3 最佳买卖股票时机含冷冻期

3.1 概述

3.1.1 题目出处

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

3.1.2 题目描述

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:

输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

3.3 动态规划 V1

3.3.1 思路

考虑四种状态的转移图如下：

• dp[i][0]代表该天不持有股票且非卖出的最大利润
  dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);
• dp[i][1] 代表该天卖出股票的最大利润
  dp[i][1] = dp[i - 1][3] + prices[i];
• dp[i][2] 代表该天位冷冻期最大利润
  dp[i][2] = dp[i - 1][1];
• dp[i][3] 代表该天卖出股票的最大利润
  dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][0] - prices[i], dp[i-1][2] - prices[i]);

初始：

// 不持股，非卖出
dp[0][0] = 0;
// 卖出
dp[0][1] = 0;
// 冷冻
dp[0][2] = 0;
// 持股
dp[0][3] = 0 - prices[0];

返回值：
最后结果是不持股的三种状态的最大值

3.3.2 代码

class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length < 2){
            return 0;
        }

        int[][] dp = new int[prices.length][4]; 
        // 不持股，非卖出
        dp[0][0] = 0;
        // 卖出
        dp[0][1] = 0;
        // 冷冻
        dp[0][2] = 0;
        // 持股
        dp[0][3] = 0 - prices[0];

        for(int i = 1; i < prices.length; i++){
            // i日为不持股非卖出，则肯定是由i-1天不持股非卖出或冷冻转移而来
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);

            // i日为卖出，则肯定是由i-1天持股且在i日卖出
            dp[i][1] = dp[i - 1][3] + prices[i];

            // i日为冷冻，则肯定是由i-1天卖出状态转移而来
            dp[i][2] = dp[i - 1][1];

            // i日为持股，则i-1天持股或（冷冻 || 不持股非卖出）且在i日买入持股
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][0] - prices[i]);
            dp[i][3] = Math.max(dp[i][3], dp[i-1][2] - prices[i]);
        }

        // 最后结果是不持股的三种状态的最大值
        int result = Math.max(dp[prices.length - 1][0], dp[prices.length - 1][1]);
        result = Math.max(result, dp[prices.length - 1][2]);

        return result;
    }
}

3.3.3 时间复杂度

O(N)

3.3.4 空间复杂度

O(N)

3.4 动态规划 V2

3.4.1 思路

这道题目最大利润也是递增，而且是只需要考虑i日和i-1日的关系，所以也已用4个变量分别记录i日的四种状态时的最大利润。

3.4.2 代码

//TODO

3.4.3 时间复杂度

O(N)

3.4.4 空间复杂度

O(1)

参考文档

• 贪心算法详解