【LeetCode】#121. Best Time to Buy and Sell Stock 詳細完整解法

Best Time to Buy and Sell Stock

題目要求

給你一組由一段時間的股票價格所組成的陣列,找出這段時間中股票買賣的最大收益。

不能在同一天進行買賣,如果沒有找到任何可以買賣的時機,回傳0。

其他限制條件

  • 股票價格的時間段長度為[1,10^5]
  • 股票價格的範圍為[0,10^4]

解題思路

沒提到的規則

這一題要先了解一下股票買賣的規則,除了上面提到的幾個限制之外,還有一些隱藏的規則是題目沒有描述到的。

  • 不能買在未來
  • 不能放空
  • 不能在同一天買賣

不能同一天買賣得規則題目已經規定了,沒提到的部分還有,股票從時間線上不能買在未來,還有做空機制在這一題是不存在的,這些部分要注意。

直覺解

雖然題目規定不能夠同一間買賣,但是以結果來說,同一天買賣等於沒有任何收益,不會影響結果。

我們先來假設幾個例子:

EX 1. [0, 10, 1, 20]:最大收益是買在[0]賣在[20]。

EX 2. [10, 50, 0, 30]:最大收益是買在[10]賣在[50],因為買在[0]賣在[30]收益只有30,比40少,雖然做空賣在[50]買在[0]可以獲得更大收益,但是這一題隱藏條件是不能放空,所以不能怎麼做。

透過兩個例子我們可以理解到,要取得最大的收益,就是買在最低點,賣在最高點。

程式碼

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //最大收益
        int maxVal=0;

	//最低價格
        int minPrice=INT_MAX;

        //計算每一天能獲得的最大收益
        for(auto i:prices){
	    //如果價格創新低,代表未來有可能獲得更高的收益,所以替換成最新的價格
            minPrice = min(minPrice,i);
            //計算每一天價格減去最低點的收益,如果收益大於最大收益,更新最大收益
            maxVal = max(maxVal,i-minPrice);
        }
        
	//返回結果
        return maxVal;
    }
};

時間複雜度分析

不到最後一天不會知道是否還會有更高的收益出現,因此要走完整個時間段,時間複雜度為O(n)。

空間複雜度分析

除了一開始宣告了最大收益和最低價格兩個變數,使用空間沒有變化,所以空間複雜度為O(1)。

在〈【LeetCode】#121. Best Time to Buy and Sell Stock 詳細完整解法〉中有 1 則留言

  1. 自動引用通知: 【LeetCode】 刷題地圖 - 人生自習室

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

回到頂端