LeetCode 問題：買賣股票的最佳時機

我最近解決了一個經典的 LeetCode 問題：「買賣股票的最佳時機」。這題要求你求出一次買賣股票所能獲得的最大利潤。讓我們深入探討我所探索過的不同方法及其複雜性。這是問題的 URL：

LeetCode 121

蠻力方法（時間複雜度：O(n^2)）

最直接的解決方案可能是將陣列中的每個元素與所有剩餘元素進行比較。對於每個價格，我們計算如果在稍後的一天出售它會產生的利潤。然後我們追蹤遇到的最大利潤。然而，這種方法的時間複雜度較高，導致 Time Limit Exceeded。

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

    let max = 0;
    for (var i = 0; i  a) return b - a;
    else return 0;
}

原因如下： 我們將每個元素與 n-1 個其他元素進行比較，從而產生 n*(n-1)/2 次比較。這大致相當於 O(n^2) 時間複雜度，對於大型資料集來說效率很低。不幸的是，這種方法經常會導致 LeetCode 出現「Time Limit Exceeded」錯誤。

二指標法（時間複雜度：O(n)）

為了提高效率，我們可以利用先買後賣的事實。我們可以引入兩個指標：

• 購買：指向當前的潛在購買價格。
• sell：指向候選售價。

這個想法是從第三個元素開始迭代價格數組（因為前兩個元素用於買賣）。我們不斷檢查賣出價（當前元素）和買入價之間的差額是否大於當前最大利潤。如果為真，我們更新最大利潤。否則，我們將買入指標更新為當前元素（可能是較低的買入價格）並將賣出指標向前移動一步。

這種方法顯著提高了時間複雜度，達到了 O(n)，因為我們只迭代數組一次。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    let maxProfit = 0;
    let buy = 0;
    let sell = 1;
    while (sell 



<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/172284027594031.png?x-oss-process=image/resize,p_40" class="lazy" alt="LeetCode 問題：買賣股票的最佳時機" loading="lazy"    style="max-width:90%"  style="max-width:90%"></p>

<h2>
  
  
  貪婪方法（時間複雜度：O(n)）與 Python 範例
</h2>

<p>我們可以透過貪心方法實現類似的時間複雜度。這裡的關鍵是要明白，只有低買高賣才能達到最大利潤。  因此，我們可以迭代價格數組並追蹤迄今為止遇到的最低價格。這代表了潛在的購買價格。 </p>

<p>這是貪婪方法的 Python 實作：<br>
</p>

<pre class="brush:php;toolbar:false">class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0;
        min_buy = float('inf')
        for price in prices:
            min_buy = min(min_buy , price )
            max_profit =  max(max_profit, price-min_buy)
        return max_profit

您可以隨時了解更多有關在我的作品集上還可以在哪裡找到我的信息

以上是LeetCode 問題：買賣股票的最佳時機的詳細內容。更多資訊請關注PHP中文網其他相關文章！