LeetCode #121 Best Time to Buy and Sell Stock 買賣股票最好的時機

內容目錄

文章觀看次數: 641

LeetCode題目翻譯

英文原文如下

You are given an array prices where prices[i] is the price of a given stock on the i^th day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

中文翻譯

給予你一個陣列 prices ，裡面放的是某支股票一段時間的價格 prices[i] = i^th 日的價格

你想要透過在一天買進並在未來的某一天賣出，來獲取最高的利潤

回傳你能獲得最高的利潤，如何沒辦法賺到任何收益，則回傳 0

範例及題目限制

範例都比較簡單，總之就是只做一次的買低賣高

範例2 中，因為完全沒有做任何交易故最高收益為 0

解題思路

講到股票，就讓人想起了今年，台股一路從萬8 跌了5000多點….

( 大家的損益都綠油油的 )

咳咳，我們先回歸正題 ( 哪天轉型寫金融文章再講講股票 )

看到這一題，大家肯定跟我一樣不到3秒就想出第一個解法了

巢狀迴圈 i 跟 j 給他跑下去 !! 每次確認是否比最大值大這樣

❌超過時間限制

public class Solution {
    public int MaxProfit(int[] prices) {
        
        int max = 0;
         for(int i = 0;i<prices.Length-1;i++)
         {
             for(int j = i+1;j<prices.Length;j++)
             {
                 int res = prices[j]-prices[i];
                 if(res>max)
                 {
                     max = res;
                 }
             }
         }
        return max;
    }
}

寫完收工! ➡ 一提交，Error 超過時間限制

時間複雜度 : O(n²)

這時我們來換一種寫法吧

首先，先設兩個變數 min 跟 max

在迴圈中，要是任一數字比 min 小，就會取代 min

另外保留了比較最大值的設計

相對第一個嘗試，最大的變化就是會動態調整最小值方便計算

整體的時間複雜度也會獲得極大的提升 O(n²) ➡ O(n)

C# 解決方案

方案1

public class Solution {
    public int MaxProfit(int[] prices) {
        int max = 0;
        int min = prices[0];
        
        for(int i=1;i<prices.Length;i++){
            if(prices[i] < min){
                min = prices[i];
            }
            
            else if((prices[i] - min) > max )
            {
                max = prices[i] - min;
            }
        }
        return max;
    }
}

時間複雜度 : O(n)

Java解決方案

方案1

class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        int min = prices[0];
        
        for(int i=1;i<prices.length;i++){
            if(prices[i] < min){
                min = prices[i];
            }
            
            else if((prices[i] - min) > max )
            {
                max = prices[i] - min;
            }
        }
        return max;
    }
}

Python3 解決方案

方案1

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max = 0;
        min = prices[0];
        
        for i in range(1,len(prices)):
            if prices[i] < min :
                min = prices[i]
            
            elif((prices[i] - min) > max):
                max = prices[i] - min
        
        return max;

JavaScript 解決方案

方案1

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    var max = 0;
    var min = prices[0];

    for(let i=1;i<prices.length;i++){
        if(prices[i] < min){
            min = prices[i];
        }

        else if((prices[i] - min) > max )
        {
            max = prices[i] - min;
        }
    }
    return max;
};

結論

要是買股票也有這麼快樂就好了…

這題是 Blind 75 中的一題，算是可以簡單考驗邏輯的題目吧

( Blind 75 之後會額外介紹，簡單來說是一個被大家認為做完就有一定基礎的LeetCode題目清單 )

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡可以的話，幫我的FaceBook 粉絲專頁按個讚，我會很感謝的

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Best Time to Buy and Sell Stock – LeetCode

LeetCode題目翻譯

解題思路

C# 解決方案

Java解決方案

Python3 解決方案

JavaScript 解決方案

結論

相關文章

LeetCode #345 Reverse Vowels of a String 反轉一個字串中的母音

LeetCode #242 Valid Anagram 正確的易位構詞遊戲

發佈留言取消回覆