第五天 122. Best Time to Buy and Sell Stock II:找出買賣股票的最佳時機。題目會給定一個歷史數據,並要求算出在這段時間中最大的獲利是多少。

第一直覺想到的是暴力解、接著有點被前幾天的 30-Day LeetCoding Challenge (Day3) - 53. Maximum Subarray 影響到,想了下是不是要記錄前面到現在的最大獲利值、是否要找出相對高點和低點。不過後來再仔細項想,其實不需要找出全局的高低點,只要判斷今天是不是比昨天還高就可以了:套用一下 Leetcode solution 的圖片來解釋,連續上升的 ABC波段相加就等於是從低谷到高鋒。

程式寫起來也很簡單明白,不過實際上股市明天到底是長是跌如果真有程式可以精準算得出來,就不會有人如此頭痛到底要買要賣了吧 😏

static int __ = [](){ std::ios::sync_with_stdio(false); return 0;}();

class Solution {
public:
    int maxProfit(vector<int>& prices) {

        int profit = 0;
        for(int i=1; i<prices.size(); i++)
            if(prices[i] > prices[i-1])
                profit += prices[i] - prices[i-1];
        return profit;
    }
};

同場加映 121. Best Time to Buy and Sell Stock,上一題不限制買賣次數,但這題只能買賣一次。最簡單的暴力解,結果TLE了。

static int __ = [](){ std::ios::sync_with_stdio(false); return 0;}();
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        
        for(int i=0; i<prices.size()-1; i++)
            for(int j=i+1; j <prices.size(); j++)
                if(prices[j] - prices[i] > profit)
                    profit = prices[j] - prices[i];
        
        return profit;
    }
};

所以思路就變成一次掃完找出最高點和最低點,一樣套用一下 Leetcode 的說明圖片,在每個時間點都記錄目前最低點以及算出和最低點的差,即時更新存下最大獲利值。

static int __ = [](){ std::ios::sync_with_stdio(false); return 0;}();
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX;
        int profit = 0;

        for(int i=0; i<prices.size(); i++) {
            minPrice = min(prices[i], minPrice);
            profit = max(prices[i] - minPrice, profit);
        }

        return profit;
    }
};

這樣就不超時拉~

發佈留言

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

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料