echo

任生命穿梭 时间的角落

0%

买卖股票

Posted on Edited on In Valine:

121. 买卖股票的最佳时机

难度：简单

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

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

示例 2：

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

提示：

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

题解：

对于只能买卖一次的股票交易，对于 prices 数组中的数对 （prices[i]，prices[j] 且i < j，求 prices[j] - prices[i] 的最大值 。

方法一：暴力枚举（代码略）

直接枚举右边界 j，然后向左枚举左边界 i, 维护最大值。

  • 时间：$O(n^2)$

  • 空间：$O(1)$

方法二：一次遍历

在遍历过程中维护最小值 minStock，省略内层循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length < 2){
            return 0;
        }
		// minStock 为 prices[0 ... i] 中最小值
        int minStock = prices[0], profit = 0;
        for(int i = 1; i < prices.length; i++){
            if(prices[i] > minStock){
                profit = Math.max(profit, prices[i] - minStock);
            }else{
                minStock = prices[i];
            }
        }
        return profit;
    }
}

  • 时间：$O(n)$

  • 空间：$O(1)$

122. 买卖股票的最佳时机 II

难度：中等

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

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

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

示例 1:

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

示例 3:

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

提示：

  • 1 <= prices.length <= 3 * 104
  • 0 <= prices[i] <= 104

题解：

方法一：动态规划

这次我们可以买卖多次股票，选择第 i - 1天和 第 i 天分析：

image-20211022165325957

第 i 天有股票的情况分两种：前一天就有股票；前一天没股票，第 i 天买了股票。

有股票时的最大利润为两者中的最大值

类似的，第 i 天没股票的情况分两种：前一天没有有股票；前一天有股票，第 i 天买了股票。

有股票时的最大利润为两者中的最大值

令 $ f[i][0]$ 为第 i 天有股票时的最大利润，令 $ f[i][1]$ 为第 i 天没股票时的最大利润，可以得到如下转移方程：
$$
f[i][0] = max(f[i - 1][0], f[i - 1][1] - prices[i])
$$

$$
f[i][1] = max(f[i - 1][1], f[i - 1][0] + prices[i])
$$

初始条件：$ f[i][0] = -prices[0]$，$ f[i][1] = 0$

第 0 天就持有股票的最大利润为负（利润为 0 时就买了第 0 天的股票），没有持有股票的最大利润为 0 。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for(int i = 1; i < prices.length; 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[n - 1][0];
    }
}

  • 时间：$O(n)$

  • 空间：$O(n)$

可以看到 第 i 天的状态只与第 i - 1天有关，可以进行空间优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int dp0 = 0, dp1 = -prices[0];
        for(int i = 1; i < prices.length; i++){
            int newdp0 = Math.max(dp0, dp1 + prices[i]);
            int newdp1 = Math.max(dp1, dp0 - prices[i]);
            dp0 = newdp0;
            dp1 = newdp1;
        }
        return dp0;
    }
}

  • 时间：$O(n)$

  • 空间：$O(1)$

方法二：贪心

由于不限制交易次数，只要今天股价比昨天高，就交易。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for(int i = 1; i < prices.length; i++){
            if(prices[i] > prices[i - 1]){
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
}

  • 时间：$O(n)$

  • 空间：$O(1)$

123. 买卖股票的最佳时机 III

难度：困难

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

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

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

示例 1:

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

示例 2：

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

示例 3：

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

示例 4：

1
2
输入：prices = [1]
输出：0

提示：

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 105

此题与 122 不同的是，限制了交易次数，只能交易两次。

类似的，我们分析一下第 i天有几个状态，第i - 1 天到第i 天的转移关系是什么样的。

我们可以将每天分为 5 个状态：没有任何买卖操作，第一次持有股票，第一次卖完股票，第二次持有股票，第二次卖完股票。由于没有任何买卖操作，利润总是 0 ，我们需要计算的只有 4 个状态。

image-20211022172452534

令 $ f[i][0]$ 为第 i 天第一次持有股票时的最大利润，令 $ f[i][1]$ 为第 i 天第一次没有股票时的最大利润，令 $ f[i][2]$ 为第 i 天第二次持有股票时的最大利润，令 $ f[i][3]$ 为第 i 天第二次没有股票时的最大利润，可以得到如下转移方程：
$$
f[i][0] = max(f[i - 1][0], - prices[i])
$$

$$
f[i][1] = max(f[i - 1][1], f[i - 1][0] + prices[i])
$$

$$
f[i][2] = max(f[i - 1][2], f[i - 1][1] - prices[i])
$$

$$
f[i][3] = max(f[i - 1][3], f[i - 1][2] + prices[i])
$$

初始条件：$ f[i][0] = f[i][2] = -prices[0]$，$ f[i][1] = f[i][3] = 0$

$f[i][2] = -prices[0]$ 可以理解为买了 prices[0]，然后立马卖了 prices[0]，再次买入 prices[0]，这样就是第二次有股票。

在考虑边界条件时我们注意到以下事实：

==无论题目中是否允许同一天买入卖出，这一操作都不会对最终结果造成影响，因为这一操作收益为零==

我们可以进一步优化上述转移方程：
$$
f[0] = max(f[0], - prices[i])
$$

$$
f[1] = max(f[1], f[0] + prices[i])
$$

$$
f[2] = max(f[2], f[1] - prices[i])
$$

$$
f[3] = max(f[3], f[2] + prices[i])
$$

对于$f[0] = max(f[0], - prices[i])$来说，这是滚动数组常用技巧，左边的 $f[0]$代表今天第一次持有股票的最大利润，右边的 $f[0]$代表昨天第一次持有股票的最大利润；

对于$f[1] = max(f[1], f[0] + prices[i])$来说，左边的 $f[1]$代表今天第一次没有股票的最大利润，右边的 $f[1]$代表昨天第一次没有股票的最大利润，此时 $f[0]$应该是代表昨天第一次持有股票的最大利润，但由于我们刚才已经把值更新为今天第一次持有股票的最大利润。为什么这样转移方程依然正确？

将今天的 f[0]带入 f[1] 计算公式中，得到$f[1] = max(f[1], max(f[0], -prices[i])+ prices[i] \ )$，此时 $f[0]$是代表昨天第一次持有股票的最大利润。我们多考虑了第 i 天买入股票的情况，但同时计算 $f[1]$时，又将股票卖出，这样的利润为 0 ,这一操作收益为零，对结果没有影响。所以我们将新的 $f[0]$值用于计算不会导致错误结果。

后面的依此类推。

最后，我们手中肯定没有股票，结果在 0, $f[1]$，$f[3]$中选择最大的，由于在状态转移中我们维护的是最大值，且$f[1]$，$f[3]$初始值为 0，0不可能为结果。如果最优解为交易一次，即$f[1]$，那么它也会因为我们在转移时允许在同一天买入并且卖出这一宽松的条件，从$f[1]$转移到$f[3]$，因此最后答案为 $f[3]$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] f = new int[4];
        // 分为 5 个阶段：没买也没卖，买了一次，卖了一次，买了两次且卖了一次，卖了两次
        f[0] = f[2] = -prices[0];
        f[1] = f[3] = 0;
        for(int i = 1; i < n; i++){
            f[0] = Math.max(f[0], -prices[i]);
            f[1] = Math.max(f[1], f[0] + prices[i]);
            f[2] = Math.max(f[2], f[1] - prices[i]);
            f[3] = Math.max(f[3], f[2] + prices[i]);
        }
        return f[3];
    }
}

  • 时间：$O(n)$

  • 空间：$O(1)$

188. 买卖股票的最佳时机 IV

难度：困难

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

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

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

示例 1：

1
2
3
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2：

1
2
3
4
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

提示：

  • 0 <= k <= 100
  • 0 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000

此题与 123 类似，但可交易 k 次，由之前的经验可以推导，每天应该有 2 * k + 1个状态。

image-20211022200055327

初始化数组 $f$ ，长度为 $2k + 1$，$f[0] = 0$ 表示没有参与任何交易的利润。$f[2j - 1]$表示第 j次*持有股票的最大利润，$f[2 * j ]$表示第j次没有股票**的最大利润，其中$1 <= j <= k$。

令 $j$ 为 数组 $f$ 下标，我们可以写出转移方程：
$$
f[j] = max(f[j], f[j - 1] - prices[i]), j 为奇数
$$

$$
f[j] = max(f[j], f[j - 1] + prices[i]), j 为偶数
$$

同样的，最后的结果为第 k 次没有股票的最大利润$f[2 * k]$。

初始条件：所有奇数下标位置为 $ -prices[0]$, 所有偶数下标位置为 0，分析过程同 123 题。

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 {
    public int maxProfit(int k, int[] prices) {
        if(prices.length == 0){
            return 0;
        }
        int n = prices.length;
        int[] f = new int[2 * k + 1];
        for(int j = 1; j <= 2 * k; j += 2){
            f[j] = -prices[0];
        }
        for(int i = 0; i < n; i++){
            for(int j = 1; j <= 2 * k; j++){
                if((j & 1) == 1){ // 买
                    f[j] = Math.max(f[j], f[j - 1] - prices[i]);
                }else{ //卖
                    f[j] = Math.max(f[j], f[j - 1] + prices[i]);
                }
            }
        }

        return f[2 * k];
    }
}

  • 时间：$O(nk)$

  • 空间：$O(k)$

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

难度：中等

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

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

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

示例:

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

显然，每天的状态有：持有股票，没有股票，冷冻期。我们画出今天和昨天的关系图：

image-20211022213057682

定义 $f[i][0]$ 第 i 天有股票， $f[i][1]$ 第 i 天无股票冷冻期， $f[i][2]$ 第 i 天无股票非冷冻期。可得到如下转移方程：
$$
f[i][0] = max(f[i - 1][0], f[i - 1][2] - prices[i])
$$

$$
f[i][1] = f[i - 1][0] + prices[i]
$$

$$
f[i][2] = max(f[i - 1][1], f[i - 1][2])
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length < 2){
            return 0;
        }
        int n = prices.length;
        int[][] f = new int[n][3];
        f[0][0] = -prices[0];
        for(int i = 1; i < n; i++){
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][2] - prices[i]);
            f[i][1] = f[i - 1][0] + prices[i];
            f[i][2] = Math.max(f[i - 1][2], f[i - 1][1]);
        }
        return Math.max(f[n - 1][1], f[n - 1][2]);
    }
}

  • 时间：$O(n)$

  • 空间：$O(n)$

我们可以只保存最近两天的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length < 2){
            return 0;
        }
        int n = prices.length;
        // f[0] 表示第 i 天持有股票时的最大利润，f[1] 表示无股票冷冻期，f[2] 表示无股票非冷冻期
        int[] f = new int[3];
        f[0] = -prices[0];
        for(int i = 1; i < n; i++){
            int[] newF = new int[3];
            newF[0] = Math.max(f[0], f[2] - prices[i]);
            newF[1] = f[0] + prices[i];
            newF[2] = Math.max(f[2], f[1]);
            f = newF;
        }
        return Math.max(f[1], f[2]);
    }
}
  • 时间：$O(n)$
  • 空间：$O(1)$

714. 买卖股票的最佳时机含手续费

难度：中等

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1：

1
2
3
4
5
6
7
8
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例 2：

1
2
输入：prices = [1,3,7,5,10,3], fee = 3
输出：6

提示：

  • 1 <= prices.length <= 5 * 104
  • 1 <= prices[i] < 5 * 104
  • 0 <= fee < 5 * 104

此题就是 121 加上卖出手续费。关系图如下：

image-20211022214139191

令 $ f[i][0]$ 为第 i 天有股票时的最大利润，令 $ f[i][1]$ 为第 i 天没股票时的最大利润，可以得到如下转移方程：
$$
f[i][0] = max(f[i - 1][0], f[i - 1][1] - prices[i])
$$

$$
f[i][1] = max(f[i - 1][1], f[i - 1][0] + prices[i] -fee)
$$

初始条件：$ f[i][0] = -prices[0]$，$ f[i][1] = 0$

只保存最近两天的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxProfit(int[] prices, int fee) {
        if(prices.length < 2){
            return 0;
        }
        int n = prices.length;
        int[] f = new int[2];
        f[0] = -prices[0];
        // f[0] 代表持有股票，f[1]代表没有股票
        for(int i = 1; i < n; i++){
            int[] newF = new int[2];
            newF[0] = Math.max(f[0], f[1] - prices[i]);
            // 卖出收手续费
            newF[1] = Math.max(f[1], f[0] + prices[i] - fee);
            f = newF;
        }
        return f[1];
    }
}

  • 时间：$O(n)$

  • 空间：$O(1)$