MediumRating 1393
978. Longest Turbulent Subarray
arraydynamic-programmingsliding-window
解題說明
Longest Turbulent Subarray
題目描述：
給定一個整數陣列 arr，找出最長的**湍流子陣列（Turbulent Subarray）**的長度。湍流子陣列的定義：相鄰元素之間的比較符號交替變化（大、小、大、小... 或 小、大、小、大...）。
解題思路： 動態規劃 / 滑動窗口：
維護兩個計數器：
inc：以arr[i]結尾且最後一步為「遞增」（arr[i-1] < arr[i]）的最長湍流子陣列長度。dec：以arr[i]結尾且最後一步為「遞減」（arr[i-1] > arr[i]）的最長湍流子陣列長度。
轉移：
- 若
arr[i] > arr[i-1]：inc = dec + 1，dec = 1（遞增步接在遞減步後面）。 - 若
arr[i] < arr[i-1]：dec = inc + 1，inc = 1。 - 若
arr[i] == arr[i-1]：inc = dec = 1（重置）。
答案為所有 max(inc, dec) 的最大值。
C++ 解法
複雜度分析
時間複雜度：O(n) — 一次遍歷陣列。
空間複雜度：O(1) — 只使用常數個變數。
虛擬碼
1. Initialize inc = 1, dec = 1, result = 1. 2. For i from 1 to n-1: a. If arr[i] > arr[i-1]: inc = dec + 1, dec = 1. b. Else if arr[i] < arr[i-1]: dec = inc + 1, inc = 1. c. Else: inc = 1, dec = 1. d. result = max(result, inc, dec). 3. Return result.
其他解法
滑動窗口：O(n) 時間、O(1) 空間。維護一個窗口 [l, r]，當 arr[r] 不滿足湍流條件時收縮左邊界。邏輯等價但需要更仔細地處理邊界條件。
符號陣列法：O(n) 時間、O(n) 空間。先建立符號陣列 sign[i] = compare(arr[i], arr[i-1])（-1, 0, 1），然後找最長的交替子陣列。增加了理解清晰度但多用了 O(n) 空間。
延伸思考
- 為什麼
inc = dec + 1是正確的轉移？直覺上為什麼遞增步要接在遞減步後面？ - 如果相等的元素也算合法（即非嚴格交替），DP 需要如何調整？
- 本題與「最長交替子序列」有何差異？子陣列 vs 子序列對演算法有什麼影響？