leetcode刷题笔记-121.买卖股票的最佳时机。这道题有很多解法，特此记录一下不同的解法思路。

题目

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

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

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

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

1
2
3
4
5
6
7
8
9
10
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
     
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

思路

暴力

暴力思路就是两层for循环，计算最大的差值，就是得到的最大利润

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxProfit = 0; // 最大收益
        for (int i = 0; i < prices.size(); i++) {
            for (int j = i + 1; j < prices.size(); j++) {
                maxProfit = max(maxProfit, prices[j] - prices[i]);
            }
        }
        return maxProfit;
    }
};

时间复杂度是O(N^2)，会超时

image.png

贪心

本题思路

贪心算法，思路是枚举当前数之前的最小值，计算当前数得到的利润的最大值。

  • 用一个元素来记录最小值，每一次遍历都更新这个最小值（最小的买入价格）
  • 用一个元素来记录得到的最大利润，每一次遍历都更新最大利润（当前价格减去最小买入价格）

首先更新的是最大利润，再更新最小买入价格，这样能保证最小买入价格的值一定是当前元素之前的某一个值，计算出来的最大利润才有效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxProfit = -1;       // 最大收益
        int minPrice = prices[0]; // 当前的最小价格
        for (auto& i : prices) {
            // 当前值减去最小价格得到最大收益
            maxProfit = max(maxProfit, i - minPrice);
            // 需要更新最小价格，保证最小价格是在当前值之前的某一个数
            minPrice = min(minPrice, i);
        }
        return maxProfit;
    }
};

image.png

122题 买卖股票的最佳时机2

这里顺带记录一下122题的贪心思路。122题在本题的基础上新增了一个可以多次卖出+买入的操作。而121题只能买入一次+未来卖出一次。

因为每一天都可以买入+卖出，所以我们可以把利润拆分成每一天。只要某一天买入+明天卖出的利润是正数，那么就把他加入到最终结果中。这样就相当于排除亏钱的情况，只要能赚钱就买，即可计算出最大利润。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 122. 买卖股票的最佳时机 II
// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int count = 0;
        // 第0天买，第3天卖的利润是prices[3]-prices[0]
        // 也等于 p[3]-p[2] + p[2]-p[1] + p[1]-p[0]
        // 所以最大利润其实就是每天利润之和（前提是利润都是正的）
        for (int i = 1; i < prices.size(); i++) {
            // 计算昨天买今天卖能获得多少利润
            // 如果大于0就加入进去
            count += max(prices[i] - prices[i - 1], 0);
        }
        return count;
    }
};

动态规划

本题思路

动态规划就要记住解题的几个步骤。

  • 确定动归数组每个下标的含义
  • 确定迭代方程
  • 确定初始值
  • 确定遍历顺序
  • 举例推导

对于这道题而言，每天都有两种状态：今天持有股票和今天卖出股票。

我们可以设定dp[i][0]是第i天持有股票时的得到的最多钱，dp[i][1]是第i天不持有股票时得到的最多钱。很容易发现每天不持有股票得到的钱是更多的，所以最终的答案就是dp[prices.size()-1][1]，即这个二维数组的右下角。

这里就需要两个递推公式了，先看第i天持有股票的钱

  • 上一天就持有股票，即保持dp[i-1][0]不变；
  • 今天才持有股票（买入），即-price[i]，本题股票只能买入一次，所以选择今天买入，那么剩下的钱就是0减去股票的价格；

可得 dp[i][0] = max(dp[i-1][0],-price[i])，上两种情况的最大值。

第i天不持有股票的钱也分为两种情况

  • 上一天就没有持有股票，即保持dp[i-1][1]不变；
  • 今天才卖出股票，即保持price[i]+dp[i-1][0]（因为今天卖出，所以上一天肯定是持有股票的）

可得递推公式 dp[i][1] = max(dp[i-1][1],price[i]+dp[i-1][0])；

初始化dp数组时，第0天肯定只能持有股票，不能卖出，所以初始化如下

1
2
dp[0][0] = 0-price[0];
dp[0][1] = 0;

这里还有另外一个优化方向，从递推公式中可以看出，每一天的值只和上一天有关系，那么并不需要一个完整的二维数组，只需要一个2*2的数组就可以了，我们把今天的值写入上一天就OK了，这样可以把空间复杂度降为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(2, vector<int>(2, 0));
        dp[0][0] = 0-prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < prices.size(); i++) {
            dp[1][0] = max(0-prices[i], dp[0][0]);
            dp[1][1] = max(prices[i] + dp[0][0], dp[0][1]);
            // 把当前值挪过去，作为上一行的结果
            dp[0][0] = dp[1][0];
            dp[0][1] = dp[1][1];
        }
        return dp[1][1];
    }
};

image.png

不过个人感觉这道题用动态规划来写实在是想不出来思路，而且还感觉很麻烦，还不如用贪心来处理一下。

122题 买卖股票的最佳时机2

同样记录一下122题的代码。122题和本题在动态规划上唯一的区别就是当天买入股票的时候，需要计算上一天卖出股票后能剩下的最多钱（因为同一天只能持有一张股票）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(2, vector<int>(2, 0));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < prices.size(); i++) {
            // 1.今天买入股票的剩余钱需要计算上一天卖出后剩下的最多钱
            // 2.今天不买入，沿用上一天的结果
            dp[1][0] = max(dp[0][1] - prices[i], dp[0][0]);
            // 1.今天卖出股票，得到的钱是上一天买入股票剩余价值+今天卖出的价格
            // 2.今天不卖出股票，沿用上一天的结果
            dp[1][1] = max(prices[i] + dp[0][0], dp[0][1]);
            // 把当前值挪过去，作为上一行的结果
            dp[0][0] = dp[1][0];
            dp[0][1] = dp[1][1];
        }
        return dp[1][1];
    }
};

The end

股票是一系列的题目，这道题只是个简单开胃菜而已！