LeetCode121 买卖股票的最佳时机

Ted

发布于：2020年12月17日
次浏览

我在LeetCode买股票之利益最大化。

今天的LeetCode每日一题很有意思，看到股票，就想到我现在的实习，虽然跟买卖股票是没有太大关系了，这道题类似的题目之前也做过几道，而且很有意思。做完这道题后我又稍微复习了一下相关的所有问题，就把这些问题的解法写下来吧。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

121. 买卖股票的最佳时机

题目描述

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

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

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

示例 1:

1
2
3
4
5
6
7
输入: [7,1,5,3,6,4]

输出: 5

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。

注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

题目解析

这道题目比较简单，因为只需要进行一次买卖，因此我们只需要在价格数组中找到按顺序的最小值，以及后面的最大值，这两个值的差值就是买卖股票获得的最大利润。我们可以使用动态规划的方法，维护两个值maxprofit和minprice，来保存最大的利润以及最小价格。在每次迭代中，minprice = min(price[i], minprice)，而maxprofit = max(maxprofit, price[i] - minprice)。通过对数组进行一次遍历，就可以得到最大的利润值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int inf = 1e9;
        int minprice = inf, maxprofit = 0;
        for (int price: prices) {
            maxprofit = max(maxprofit, price - minprice);
            minprice = min(price, minprice);
        }
        return maxprofit;
    }
};

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

题目描述

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

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

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

示例 1:

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

题目解析

这道题与上一道非常相似，不同之处在于可以进行多次买卖，甚至可以当天买入，当天卖出。但同时，个人手中不可以持有多只股票。这样，我们可以根据手中股票的状态来进行动态规划。我们可以假设dp0代表手中没有股票时，买卖股票所得到总利润，dp1代表手中持有一只股票时，买卖股票所得的总利润，类似上一道题，继续使用动态规划的方法。

我们可以得到dp0[n] = max(dp0[n - 1], dp1[n - 1] + prices[i])。我们当前手中没有股票，那么可能我们在上一天手中也没有股票，或者上一天将手中的股票卖了出去。

同样，可以得到dp1[n] = max(dp1[n - 1], dp0[n - 1] - prices[i])。如果我们手中有股票，那么可能我们在上一天也持有该股票，或者上一天刚刚买入该股票。

这样，我们再次对于数组进行一次遍历，就能得到能得到的最大利润。由于dp1肯定比dp0小（最后一天所处的状态一定是手中没有股票的，这样才能收回买卖股票所得的全部本金及利润。），所以我们直接返回dp0。

值得一提的是，因为我们在每次迭代中，只用到了dp1[n], dp0[n], dp1[n - 1], dp0[n - 1]这四个值，所以我们可以使用四个int常亮保存这四个值，这样可以节省一定的空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int dp00 = 0;
        int dp11 = -prices[0];
        int dp0 = dp00, dp1 = dp11;
        for(int i = 1; i < prices.size(); i++){
            dp0 = max(dp00, dp11 + prices[i]);
            dp1 = max(dp11, dp00 - prices[i]);
            dp00 = dp0;
            dp11 = dp1;
        }
        return dp0;
    }
};

另一个办法

其实，这道题还可以有另一种巧妙的解法。由于题目没有限制买卖的次数，我们可以用一种贪心的策略，即细分到每一天考虑，如果第二天的股票价格比第一天价格高，那就执行“第一天买，第二天卖”的策略，这样只要股票价格有上涨的趋势，那我们就一定能买到所有上涨的股票。（我还不太会具体的证明）。

换一句话说，将股票的价格画成一个折线图，我们要找的就是折线图中所有上升的区间。

于是这样再写代码就容易多了，只需要每天进行判断就可以了

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

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

题目描述

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

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

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

示例 1:

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

题目解析

这道题同样也是买卖股票，在上一道题的基础上，增加了冷冻期这一概念。说到底，只是相当于在动态规划中再次添加一个状态，也就是处于冷冻期的状态。这样就很好理解了。我第一次看到这个题时，还想了大半天怎么在上一道题的两个状态上加上各种限制，其实都不如再加上另一个状态省事。我们加上第三个状态dp10，代表此时正处于冷却期。则：dp10[i] = dp1[i - 1] + prices[i];， 如果要进入冷却期，则上一天一定持有股票，并在这天卖掉了股票。
其余的状态与上一道题类似。

我们再进行一次遍历，获得最后的利润。由于我们最后的状态可以是在冷却期，或是不持有股票也不在冷却期。所以我们要取dp0与dp10的最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(!n)return 0;
        int dp0[n], dp1[n], dp10[n];
        dp0[0] = 0;
        dp1[0] = -prices[0];
        dp10[0] = 0;
        for(int i = 1; i < n; i++){
            dp0[i] = max(dp0[i - 1], dp10[i - 1]);
            dp1[i] = max(dp0[i - 1] - prices[i], dp1[i - 1]);
            dp10[i] = dp1[i - 1] + prices[i];
        }
        return max(dp0[n - 1], dp10[n - 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.

题目解析

这道题也是在122的基础上，添加了手续费的概念，每次交易都需要支付一定手续费，这样我们可以直接在122的基础上，为每次交易添加上手续费。然后一次遍历就能得到答案了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        int dp0[n], dp1[n];
        dp0[0] = 0;
        dp1[0] = -prices[0] - fee;
        for(int i = 1; i < prices.size(); i++){
            dp0[i] = max(dp0[i - 1], dp1[i - 1] + prices[i]);
            dp1[i] = max(dp1[i - 1], dp0[i - 1] - prices[i] - fee);
        }
        return dp0[n - 1];
    }
};

最后更新于：2020年12月29日

LeetCode

动态规划

评论