$\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{Language: C++}$

$\textrm{Label: Dynamic Program}$

$\textrm{Solution:}$

买卖股票问题的基本框架是,你能够知道某只股票接下来$\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,在该问题中,买卖股票的次数被改成了无限制,也就是说每一天我们都可以有选择的进行买/卖的操作。我们首先考虑几个情景:

  1. 你在第$\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]}$,可以看到效果是完全一样的。也就是说在保证某个序列为递增序列时,我们可以直接加上相邻两个数之间的差值,因为无论卖出与否,意义都是一样的。
  2. 然后考虑出现递减序列的情景,如$\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)

$\textrm{Author}$@$\href{http://kuroko.info}{\textrm{Kuroko}}$

$\textrm{GitHub}$@$\href{https://github.com/SuperKuroko}{\textrm{SuperKuroko}}$

$\textrm{LeetCode}$@$\href{https://leetcode-cn.com/u/kuroko177/}{\textrm{kuroko177}}$

$\textrm{Last Modified: 2021-01-09 16:04}$