Medium

题目描述

给定一个整数数组 arr，返回 arr 的最大湍流子数组的长度。

如果比较符号在子数组中的每对相邻元素之间都发生翻转，则该子数组是湍流的。

更正式地说，当且仅当下列条件之一成立时，数组 [arr[i], arr[i + 1], ..., arr[j]] 是湍流的：

  • 对于 i <= k < j：

    • 当 k 为奇数时，arr[k] > arr[k + 1]
    • 当 k 为偶数时，arr[k] < arr[k + 1]

  • 或者，对于 i <= k < j：

    • 当 k 为偶数时，arr[k] > arr[k + 1]
    • 当 k 为奇数时，arr[k] < arr[k + 1]

示例 1：

输入：arr = [9,4,2,10,7,8,8,1,9]
输出：5
解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

示例 2：

输入：arr = [4,8,12,16]
输出：2

示例 3：

输入：arr = [100]
输出：1

提示：

  • 1 <= arr.length <= 4 * 10^4
  • 0 <= arr[i] <= 10^9

解题思路

解题思路

湍流子数组要求相邻元素之间的比较符号交替变化，即 > 和 < 交替出现。

方法一：滑动窗口（推荐） 维护两个状态：

  • inc：以当前位置结尾且最后一个比较是递增的最长湍流子数组长度
  • dec：以当前位置结尾且最后一个比较是递减的最长湍流子数组长度

对于每个位置 i，根据 arr[i-1] 和 arr[i] 的关系更新状态：

  • 如果 arr[i-1] < arr[i]，则 inc = dec + 1，dec = 1
  • 如果 arr[i-1] > arr[i]，则 dec = inc + 1，inc = 1
  • 如果 arr[i-1] == arr[i]，则 inc = dec = 1

方法二：动态规划 定义 dp[i][0] 表示以位置 i 结尾且 arr[i-1] < arr[i] 的最长湍流子数组长度，dp[i][1] 表示以位置 i 结尾且 arr[i-1] > arr[i] 的最长湍流子数组长度。

两种方法的时间复杂度都是 O(n)，空间复杂度分别是 O(1) 和 O(n)，因此推荐滑动窗口方法。

代码实现

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        if (n <= 1) return n;
        
        int inc = 1, dec = 1;
        int maxLen = 1;
        
        for (int i = 1; i < n; i++) {
            if (arr[i-1] < arr[i]) {
                inc = dec + 1;
                dec = 1;
            } else if (arr[i-1] > arr[i]) {
                dec = inc + 1;
                inc = 1;
            } else {
                inc = dec = 1;
            }
            maxLen = max(maxLen, max(inc, dec));
        }
        
        return maxLen;
    }
};

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        n = len(arr)
        if n <= 1:
            return n
        
        inc = dec = 1
        max_len = 1
        
        for i in range(1, n):
            if arr[i-1] < arr[i]:
                inc = dec + 1
                dec = 1
            elif arr[i-1] > arr[i]:
                dec = inc + 1
                inc = 1
            else:
                inc = dec = 1
            
            max_len = max(max_len, inc, dec)
        
        return max_len

public class Solution {
    public int MaxTurbulenceSize(int[] arr) {
        int n = arr.Length;
        if (n <= 1) return n;
        
        int inc = 1, dec = 1;
        int maxLen = 1;
        
        for (int i = 1; i < n; i++) {
            if (arr[i-1] < arr[i]) {
                inc = dec + 1;
                dec = 1;
            } else if (arr[i-1] > arr[i]) {
                dec = inc + 1;
                inc = 1;
            } else {
                inc = dec = 1;
            }
            maxLen = Math.Max(maxLen, Math.Max(inc, dec));
        }
        
        return maxLen;
    }
}

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxTurbulenceSize = function(arr) {
    const n = arr.length;
    if (n <= 1) return n;
    
    let inc = 1, dec = 1;
    let maxLen = 1;
    
    for (let i = 1; i < n; i++) {
        if (arr[i-1] < arr[i]) {
            inc = dec + 1;
            dec = 1;
        } else if (arr[i-1] > arr[i]) {
            dec = inc + 1;
            inc = 1;
        } else {
            inc = dec = 1;
        }
        maxLen = Math.max(maxLen, inc, dec);
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度滑动窗口动态规划
时间复杂度O(n)O(n)
空间复杂度O(1)O(n)

其中 n 为数组长度。推荐使用滑动窗口方法，空间复杂度更优。

相关题目