題目描述:
給定一個整數陣列 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) 的最大值。
時間複雜度: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 是正確的轉移?直覺上為什麼遞增步要接在遞減步後面?