( ੭ ˙ᗜ˙ )੭
嗨，我是wec，今天是DAY 19。

🔎 題目難度與描述

難度：MEDIUM

題目描述：

給定一個整數數組nums，找出其擺動序列的最大長度。擺動序列是指一個數列中相鄰元素之間的差值交替正負的數列。

🔎 解題思路＆程式碼

1️⃣ 迭代

第1步： 設一個計數器count，初始值設為 1（至少有一個元素）。設prev_diff為 0，用來記錄前一對相鄰元素的差值。
第2步： 從 1 開始遍歷數組nums。對於每個相鄰元素，計算它們的差值diff。
第3步： 如果diff大於0且prev_diff小於或等於0（代表從下降變成上升）：增加計數器count，並更新prev_diff為當前diff。(若大於等於0就代表從上升變成下降)
第4步： 返count的值，即為最大擺動序列的長度。
程式碼：

def wiggle_max_length(nums)
  return 0 if nums.empty?
  
  count = 1
  prev_diff = 0

  (1...nums.length).each do |i|
    diff = nums[i] - nums[i - 1]
    if (diff > 0 && prev_diff <= 0) || (diff < 0 && prev_diff >= 0)
      count += 1
      prev_diff = diff
    end
  end
  
  count
end

🔎 總結

時間複雜度

迭代法： 時間複雜度為O(n)，n為組數長度。
➡️ 理解什麼是擺動序列比較重要，要會使用數字之間的差值來判斷有沒有出現擺動，所以我們可以透過記錄當前的變化（上升或下降），在一次遍歷中找到最大擺動序列的長度，而且因為只需要看一遍數組，不用反覆計算，節省了時間和精力›⩊‹!!

那麽，以上就是今天的內容！

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃北海鱈魚香絲。
明天要說：Ruby精選刷題！Medium路跑D-12(>∀･)⌒☆