LeetCode - #123 買賣股票的最佳時機 III

語言: CN / TW / HK

持續創作,加速成長!這是我參與「掘金日新計劃 · 6 月更文挑戰」的第34天,點選檢視活動詳情

前言

我們社群陸續會將顧毅(Netflix 增長黑客,《iOS 面試之道》作者,ACE 職業健身教練。)的 Swift 演算法題題解整理為文字版以方便大家學習與閱讀。

LeetCode 演算法到目前我們已經更新到 122 期,我們會保持更新時間和進度(週一、週三、週五早上 9:00 釋出),每期的內容不多,我們希望大家可以在上班路上閱讀,長久積累會有很大提升。

不積跬步,無以至千里;不積小流,無以成江海,Swift社群 伴你前行。如果大家有建議和意見歡迎在文末留言,我們會盡力滿足大家的需求。

難度水平:困難

1. 描述

給定一個數組,它的第 i 個元素是一支給定的股票在第 i 天的價格。

設計一個演算法來計算你所能獲取的最大利潤。你最多可以完成 兩筆 交易。

注意: 你不能同時參與多筆交易(你必須在再次購買前出售掉之前的股票)。

2. 示例

示例 1

輸入:prices = [3,3,5,0,0,3,1,4] 輸出:6 解釋:在第 4 天(股票價格 = 0)的時候買入,在第 6 天(股票價格 = 3)的時候賣出,這筆交易所能獲得利潤 = 3-0 = 3 。 隨後,在第 7 天(股票價格 = 1)的時候買入,在第 8 天 (股票價格 = 4)的時候賣出,這筆交易所能獲得利潤 = 4-1 = 3 。

示例 2

輸入:prices = [1,2,3,4,5] 輸出:4 解釋:在第 1 天(股票價格 = 1)的時候買入,在第 5 天 (股票價格 = 5)的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接連購買股票,之後再將它們賣出。 因為這樣屬於同時參與了多筆交易,你必須在再次購買前出售掉之前的股票。

示例 3

輸入:prices = [7,6,4,3,1] 輸出:0 解釋:在這個情況下, 沒有交易完成, 所以最大利潤為 0。

示例 3

輸入:prices = [1] 輸出:0

約束條件:

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^5

3. 答案

```swift class BestTimeBuySellStockIII { func maxProfit(_ prices: [Int]) -> Int { guard prices.count > 0 else { return 0 }

    var maxProfit = 0
    var finalMaxProfit = 0
    var maxProfitLeft = [Int]()
    var low = prices.first!
    var high = prices.last!

    for price in prices {
        maxProfit = max(price - low, maxProfit)
        low = min(price, low)
        maxProfitLeft.append(maxProfit)
    }

    maxProfit = 0

    for i in (0..<prices.count).reversed() {
        let price = prices[i]
        maxProfit = max(high - price, maxProfit)
        high = max(price, high)
        finalMaxProfit = max(finalMaxProfit, maxProfit + maxProfitLeft[i])
    }

    return finalMaxProfit
}

} ```

  • 主要思想:動態規劃,找到 [0,i][i, count - 1] 的和最大的點。
  • 時間複雜度: O(n)
  • 空間複雜度: O(n)

該演算法題解的倉庫:LeetCode-Swift

點選前往 LeetCode 練習

關於我們

我們是由 Swift 愛好者共同維護,我們會分享以 Swift 實戰、SwiftUI、Swift 基礎為核心的技術內容,也整理收集優秀的學習資料。