Leetcode-买卖股票最佳时机专题

$\textrm{Problem Description : }$

$\href{https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/}{\textrm{LeetCode121—Best Time to Buy and Sell Stock/买卖股票的最佳时机}}$
$\href{https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/}{\textrm{LeetCode122—Best Time to Buy and Sell Stock II/买卖股票的最佳时机II}}$
$\href{https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/}{\textrm{LeetCode123—Best Time to Buy and Sell Stock III/买卖股票的最佳时机III}}$
$\href{https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/}{\textrm{LeetCode188—Best Time to Buy and Sell Stock IV/买卖股票的最佳时机IV}}$
$\href{https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/}{\textrm{LeetCode309—Best Time to Buy and Sell Stock with Cooldown/最佳买卖股票时机含冷冻期}}$
$\href{https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/}{\textrm{LeetCode714—Best Time to Buy and Sell Stock with Transaction Fee/买卖股票的最佳时机含手续费}}$

买卖股票问题的基本框架是，你能够知道某只股票接下来$\textrm{n}$天的价格，我们用数组$\textrm{prices[n]}$表示。每天你可以选择买入或卖出股票，你可以拥有的最大股票数量始终为$\textrm{1}$，这意味着如果你手上已经有一支股票了，那么在卖出它之前你无法买入新的股票。上文放置了六道题目的超链接，其中前四题的区别都在于可交易次数，后两道题分别引入了冷冻期与手续费的概念。无论何种情景，我们的目标都是求出可以获取的最大利润。

我们从最简单的LeetCode121—买卖股票的最佳时机开始，在该问题中，设定的最大交易次数为$\textrm{1}$，也就是说，最多只能进行$\textrm{1}$次买入和$\textrm{1}$次卖出操作。我们假定在第$\textrm{u}$天买入股票，第$\textrm{v}$天卖出股票，于是$\textrm{answer = $(prices[v]-prices[u])_{max}$}$，其中$\textrm{u<v}$。解题思路很清晰$\textrm{:}$我们枚举卖出的天数$\textrm{v}$，数组，用$\textrm{minv}$表示当前已经遍历的元素中的最小值，做差即为候选答案之一，然后再从所有候选答案中挑选最大值。

//LeetCode121—买卖股票的最佳时机
class Solution 
{
public:
    int maxProfit(vector<int>& prices) 
    {
        if(prices.size() < 2) return 0;
        int minv = prices[0],ans = 0;
        for(int v = 0;v < prices.size();v++)
        {
            minv = min(prices[v],minv);   //更新最小值
            ans = max(ans,prices[v]-minv);//更新答案
        }
        return ans;
    }
};

时间复杂度：$O(n)$，仅遍历了一遍数组

空间复杂度：$O(1)$，只使用了常数个变量

然后我们进入第二个问题LeetCode122—买卖股票的最佳时机II，在该问题中，买卖股票的次数被改成了无限制，也就是说每一天我们都可以有选择的进行买/卖的操作。我们首先考虑几个情景:

你在第$\textrm{k}$天买入一只股票，在第$\textrm{k+2}$天将其卖出，假设$\textrm{prices[k+2]>prices[k]}$，那么你的收入是$\textrm{prices[k+2]-prices[k]}$。但是如果你在第$\textrm{k+1}$天同时进行了卖出和买入操作呢$\textrm{?}$那么收入变为$\textrm{(prices[k+2]-prices[k+1])+(prices[k+1]-prices[k]) = prices[k+2]-prices[k]}$，可以看到效果是完全一样的。也就是说在保证某个序列为递增序列时，我们可以直接加上相邻两个数之间的差值，因为无论卖出与否，意义都是一样的。
然后考虑出现递减序列的情景，如$\textrm{[5,2,3]}$，我们正确的做法是$\textrm{[2]}$买入，$\textrm{[3]}$卖出。$\textrm{ [5,6,3]}$则是$\textrm{[5]}$买入，$\textrm{[6]}$卖出。可见，当出现递减序列的时候，买入与卖出就变成了可选项。

综合上述两种情景，我们可以将相邻两个数划分成两种情况:

$\textrm{prices[i]>prices[i-1]}$，那么直接加上$\textrm{prices[i]-prices[i-1]}$，因为在这之后如果仍是增序列，那么在$\textrm{i+1}$卖出时，无论第$\textrm{i}$天操作与否，结果是一样的。而若之后是减序列，那么显然就需要在第$\textrm{i}$天卖出了。
$\textrm{prices[i]<prices[i-1]}$，不做任何操作，在这之后如果仍是增序列，那么在$\textrm{i+1}$卖出时，得到的收入是$\textrm{prices[i+1]-prices[i]}$，大于$\textrm{prices[i+1]-prices[i-1]}$，而若之后是减序列，那么这种状态被继续传递。

根据这种思想，我们可以很容易得出以下代码:(关于本题，力扣官方题解还有DP版本)

class Solution {
public:
    int maxProfit(vector<int>& prices) {   
        int ans = 0;
        int n = prices.size();
        for (int i = 1; i < n; ++i) 
            ans += max(0, prices[i] - prices[i - 1]);
        return ans;
    }
};

时间复杂度：$O(n)$，仅遍历了一遍数组

空间复杂度：$O(1)$，只使用了常数个变量

更新进度(2/6)

Author@Kuroko

GitHub@SuperKuroko

LeetCode@kuroko177

Last Modified: 2021-01-09 16:04