題目敘述
Given an integer array arr, return the length of a maximum size turbulent subarray of arr.
A subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.
More formally, a subarray [arr[i], arr[i + 1], ..., arr[j]] of arr is said to be turbulent if and only if:
- For
i <= k < j:
arr[k] > arr[k + 1] when k is odd, andarr[k] < arr[k + 1] when k is even.
- Or,
for i <= k < j:
arr[k] > arr[k + 1] when k is even, andarr[k] < arr[k + 1] when k is odd.
Example 1:
Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
Example 2:
Input: arr = [4,8,12,16]
Output: 2
Example 3:
Input: arr = [100]
Output: 1
Constraints:
1 <= arr.length <= 4 * 10^40 <= arr[i] <= 10^9
題目翻譯
題目會給一個參數 arr，要從這參數中找出最長的 "涓流" 子陣列。
何謂 "涓流"，就是指在子陣列中，相鄰的元素的比較會相反。
範例：
arr = [4,8,2,16]
arr[0] < arr[1] --> 4 < 8 --> 小於
arr[1] > arr[2] --> 8 > 2 --> 反轉成大於
arr[2] < arr[3] --> 2 < 16 --> 再反轉成小於
整個 arr 都是涓流，所以最後回傳總長度 len(arr) = 4
解法解析
這題的標準解法是使用 Dynamic programming (DP)，遍歷 arr 的所有元素，去比較跟上一比元素和下一個元素之間是否有反轉。然後紀錄起始位置。
以下的程式範例大多使用了兩個變數來記錄其值 odd 或是 even 的值，然後取最大值。
// 以 javascript 範例為準
arr = [4,8,2,16]
oddTurb--- 1
evenTurb--- 1
maxLen--- 1
oddTurb--- 2
evenTurb--- 1
maxLen--- 2
oddTurb--- 3
evenTurb--- 1
maxLen--- 3
oddTurb--- 4
evenTurb--- 1
maxLen--- 4
程式範例
Python
class Solution:
def maxTurbulenceSize(self, arr: List[int]) -> int:
N = len(arr)
ans = 1
anchor = 0
for i in range(1, N):
c = self.cmp(arr[i-1], arr[i])
if c == 0:
anchor = i
elif i == N-1 or c * self.cmp(arr[i], arr[i+1]) != -1:
ans = max(ans, i - anchor + 1)
anchor = i
return ans
def cmp(self, x, y):
if x > y:
return 1
elif x < y:
return -1
elif x == y:
return 0
JavaScript
var maxTurbulenceSize = function (arr) {
let oddTurb = 1;
let evenTurb = 1;
let maxLen = 1;
for (let k = 0; k < arr.length - 1; k++) {
if (k % 2 == 1) {
oddTurb = arr[k] > arr[k + 1] ? oddTurb + 1 : 1;
evenTurb = arr[k] < arr[k + 1] ? evenTurb + 1 : 1;
} else {
evenTurb = arr[k] > arr[k + 1] ? evenTurb + 1 : 1;
oddTurb = arr[k] < arr[k + 1] ? oddTurb + 1 : 1;
}
maxLen = Math.max(maxLen, oddTurb, evenTurb);
}
return maxLen;
};
Go
func maxTurbulenceSize(arr []int) int {
inc := 1
dec := 1
res := 1
for i := 1; i < len(arr); i++ {
if arr[i-1] > arr[i] {
dec = inc + 1
inc = 1
} else if arr[i-1] < arr[i] {
inc = dec + 1
dec = 1
} else {
inc = 1
dec = 1
}
res = max(res, max(dec, inc))
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Swift
class Solution {
func maxTurbulenceSize(_ arr: [Int]) -> Int {
guard arr.count > 1 else { return arr.count }
var res = 1
var dir = arr[1] < arr[0]
var curr = 2
for i in 1..<arr.count {
let lessThan = arr[i] < arr[i-1]
if arr[i] == arr[i-1] {
curr = 1
} else {
curr = (dir != lessThan) ? curr + 1 : 2
}
dir = lessThan
res = max(res, curr)
}
return res
}
}
Kotlin
class Solution {
fun maxTurbulenceSize(arr: IntArray): Int {
var o = 1; var e = 1; var r = 1
for (i in 0..arr.size-2) {
o = if ((i % 2 != 0 && arr[i] > arr[i+1]) || (i % 2 == 0 && arr[i] < arr[i+1])) o + 1 else 1
e = if ((i % 2 == 0 && arr[i] > arr[i+1]) || (i % 2 != 0 && arr[i] < arr[i+1])) e + 1 else 1
r = maxOf(r, o, e)
}
return r
}
}