給定一個整數陣列
arr，回傳最長的湍流子陣列長度。湍流子陣列是指相鄰元素之間的比較符號交替出現（大小大小… 或 小大小大…）。
Example:
Input: arr = [9,4,2,10,7,8,8,1,9] Output: 5 (子陣列 [4,2,10,7,8])
Intuition
TIP
維護兩個狀態：以「上升」結尾和以「下降」結尾的最長湍流長度。
inc：以當前元素結尾、最後一步是上升的湍流長度dec：以當前元素結尾、最後一步是下降的湍流長度- 若
arr[i] > arr[i-1]，則inc = dec + 1，dec = 1 - 若
arr[i] < arr[i-1]，則dec = inc + 1，inc = 1 - 若相等，兩者都重置為 1
Approaches
1. Brute Force — O(n^2) / O(1)
- Idea: 枚舉每個起點，擴展到不再湍流為止。
- Time:
O(n^2) - Space:
O(1)
class Solution {
fun maxTurbulenceSize(arr: IntArray): Int {
val n = arr.size
var result = 1
for (i in 0 until n) {
var j = i + 1
if (j < n && arr[j] == arr[i]) continue
while (j < n) {
if (j == i + 1 && arr[j] != arr[i]) {
j++
} else if (j >= i + 2 &&
(arr[j] - arr[j - 1]).toLong() * (arr[j - 1] - arr[j - 2]).toLong() < 0) {
j++
} else break
}
result = maxOf(result, j - i)
}
return result
}
}⭐ 2. State DP (Greedy) — O(n) / O(1)
- Idea: 一次遍歷，維護
inc和dec兩個計數器，根據相鄰元素大小關係更新。 - Time:
O(n) - Space:
O(1)
class Solution {
fun maxTurbulenceSize(arr: IntArray): Int {
var inc = 1 // 最後一步上升的湍流長度
var dec = 1 // 最後一步下降的湍流長度
var result = 1
for (i in 1 until arr.size) {
when {
arr[i] > arr[i - 1] -> {
inc = dec + 1
dec = 1
}
arr[i] < arr[i - 1] -> {
dec = inc + 1
inc = 1
}
else -> {
inc = 1
dec = 1
}
}
result = maxOf(result, inc, dec)
}
return result
}
}🔑 Takeaways
- Pattern: 狀態機 DP — 維護「上升結尾」和「下降結尾」兩個狀態
- Key trick: 湍流 = 交替比較符號；用兩個計數器交叉更新即可，等號時全部重置