978. Longest Turbulent Subarray

Medium

Description

給定一個整數陣列 arr，回傳最長的湍流子陣列長度。湍流子陣列是指相鄰元素之間的比較符號交替出現（大小大小… 或小大小大…）。

Example:

Input: arr = [9,4,2,10,7,8,8,1,9] Output: 5 (子陣列 [4,2,10,7,8])

Intuition#

維護兩個狀態：以「上升」結尾和以「下降」結尾的最長湍流長度。

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: 暴力#

概念: 枚舉每個起點，擴展到不再湍流為止。
時間複雜度: O(n^2)
空間複雜度: 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: 狀態 DP（Greedy）#

概念: 一次遍歷，維護 inc 和 dec 兩個計數器，根據相鄰元素大小關係更新。
時間複雜度: O(n)
空間複雜度: 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 — 維護「上升結尾」和「下降結尾」兩個狀態
關鍵技巧: 湍流 = 交替比較符號；用兩個計數器交叉更新即可，等號時全部重置