978. Longest Turbulent Subarray

題目敘述

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, and
  • arr[k] < arr[k + 1] when k is even.
• Or, for i <= k < j:
  • arr[k] > arr[k + 1] when k is even, and
  • arr[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^4
• 0 <= 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

/**
 * @param {number[]} arr
 * @return {number}
 */
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
    }
}