LeetCode - #121 買賣股票的最佳時機(Top 100)

語言: CN / TW / HK

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

前言

本題為 LeetCode 前 100 高頻題

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

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

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

難度水平:簡單

1. 描述

給定一個數組 prices ,它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格。

你只能選擇 某一天 買入這隻股票,並選擇在 未來的某一個不同的日子 賣出該股票。設計一個演算法來計算你所能獲取的最大利潤。

返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤,返回 0

2. 示例

示例 1

輸入:[7,1,5,3,6,4] 輸出:5 解釋:在第 2 天(股票價格 = 1)的時候買入,在第 5 天(股票價格 = 6)的時候賣出,最大利潤 = 6-1 = 5 。 注意利潤不能是 7-1 = 6, 因為賣出價格需要大於買入價格;同時,你不能在買入前賣出股票。

示例 2

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

約束條件:

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

3. 答案

```swift class BestTimeBuySellStock { func maxProfit(prices: [Int]) -> Int { guard prices.count > 0 else {return 0} var maxProfit = 0 var buyDay = 0

    for i in 1 ..< prices.count {
        let profit = prices[i] - prices[buyDay]
        if profit < 0 {
            buyDay = i
        }
        maxProfit = max(profit, maxProfit)
    }

    return maxProfit
}

} ```

  • 主要思想:動態程式設計,迭代陣列,當有更小的值時更改最低值,並更新結果。
  • 時間複雜度: O(n)
  • 空間複雜度: O(1)

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

點選前往 LeetCode 練習

關於我們

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