摘要

今天我們要聊的是 LeetCode 第 376 題 —— 擺動序列。
題目的意思其實很有意思：如果一個序列里的相鄰差值能保持正負交替，就叫做“擺動”。比如 [1, 7, 4, 9, 2, 5]，它就像過山車一樣，上下起伏，非常符合“擺動”的定義。

這道題的目標就是：從給定數組中找到最長的擺動子序列長度。
我會帶你先理解題意，再分析解法，最后用 Swift 寫出可運行的 Demo，并結合實際場景讓這個抽象的問題更容易理解。

描述

題目要求我們找到數組中最長的擺動子序列：

• 如果相鄰兩個數的差嚴格正負交替，那么就是擺動序列。
• 一個數字或者兩個不相等的數字也算擺動序列。
• 允許我們刪掉一些數，但不能打亂順序。

比如：

• [1, 7, 4, 9, 2, 5] → 差值是 (6, -3, 5, -7, 3)，完全正負交替，長度就是 6。
• [1, 17, 10, 13, 10, 16, 8] → 差值 (16, -7, 3, -3, 6, -8)，長度是 7。
• [1, 2, 3, 4, 5, 6, 7, 8, 9] → 最長只有兩個數，因為它一直是遞增，沒有“起伏”。

題解答案

這道題的本質是一個 動態規劃 + 貪心思想 的組合問題。
我們只需要關心當前“趨勢”：

• 如果當前差值是正的，就意味著我們找到了一個“上升擺動”。
• 如果當前差值是負的，就意味著我們找到了一個“下降擺動”。

于是，我們可以用兩個變量來動態記錄：

• up[i] 表示以第 i 個元素結尾的最長上升擺動序列長度。
• down[i] 表示以第 i 個元素結尾的最長下降擺動序列長度。

狀態轉移關系：

• 如果 nums[i] > nums[i-1]：

  • up[i] = down[i-1] + 1

• 如果 nums[i] < nums[i-1]：

  • down[i] = up[i-1] + 1

• 如果相等，啥也不變。

最后結果就是 max(up[n-1], down[n-1])。

這個邏輯其實就像我們生活中“情緒波動”一樣：

• 當你心情一直很嗨（遞增），突然遇到挫折（下降），這時候才算一次“擺動”；
• 當你心情很低落（下降），突然遇到好事（上升），又算一次“擺動”。
  如果一直高歌猛進或者持續低迷，就沒有擺動。

題解代碼分析

下面我們用 Swift 來實現：

import Foundationclass Solution {func wiggleMaxLength(_ nums: [Int]) -> Int {if nums.count < 2 { return nums.count }var up = 1var down = 1for i in 1..<nums.count {if nums[i] > nums[i - 1] {up = down + 1} else if nums[i] < nums[i - 1] {down = up + 1}}return max(up, down)}
}

代碼解析

1. 初始化
   如果數組長度小于 2，直接返回數組長度。因為一個數或兩個不相等的數就是擺動序列。

2. 定義變量
   up 和 down 初始值都設為 1。代表至少可以形成一個單獨的數字序列。

3. 遍歷數組

   • 如果當前數比前一個大，說明找到一個上升趨勢，于是 up = down + 1。
   • 如果當前數比前一個小，說明找到一個下降趨勢，于是 down = up + 1。
   • 如果相等，不做任何更新。

4. 返回結果
   最后返回 max(up, down)，即最長的擺動子序列。

示例測試及結果

我們來跑幾個例子驗證一下：

let solution = Solution()print(solution.wiggleMaxLength([1, 7, 4, 9, 2, 5]))  
// 輸出: 6print(solution.wiggleMaxLength([1, 17, 5, 10, 13, 15, 10, 5, 16, 8]))  
// 輸出: 7print(solution.wiggleMaxLength([1, 2, 3, 4, 5, 6, 7, 8, 9]))  
// 輸出: 2

輸出結果：

6
7
2

結果和題目示例完全一致。

時間復雜度

我們只遍歷了一次數組，每個元素只做了常數操作。
因此時間復雜度是 O(n)。

空間復雜度

我們只用了常數個變量 up 和 down，不需要額外存儲數組。
因此空間復雜度是 O(1)。

總結

這道題的關鍵點在于：

• 不要陷入“暴力枚舉所有子序列”的陷阱。那樣復雜度太高。
• 只需要用兩個變量跟蹤“上升”和“下降”的最長長度，就能搞定。

從實際場景來看，它就像分析“股市行情”或“人的情緒波動”：

• 如果股價總是漲（或總是跌），最長的擺動長度就很小。
• 如果股價能反復起伏，擺動序列就會變長。
  所以這個算法思路不僅能解決題目，還能幫助我們理解“變化趨勢”在數據分析里的意義。