You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

978. 最长湍流子数组 - Longest Turbulent Subarray

. 3 min read
当 A 的子数组 A[i], A[i+1], ..., A[j] 满足下列条件时,我们称其为湍流子数组:

若 i <= k < j,当 k 为奇数时, A[k] > A[k+1],且当 k 为偶数时,A[k] < A[k+1];
或 若 i <= k < j,当 k 为偶数时,A[k] > A[k+1] ,且当 k 为奇数时, A[k] < A[k+1]。
也就是说,如果比较符号在子数组中的每个相邻元素对之间翻转,则该子数组是湍流子数组。

返回 A 的最大湍流子数组的长度。

Example:

示例 1:

输入:[9,4,2,10,7,8,8,1,9]
输出:5
解释:(A[1] > A[2] < A[3] > A[4] < A[5])

示例 2:

输入:[4,8,12,16]
输出:2

示例 3:

输入:[100]
输出:1

提示:

  1. 1 <= A.length <= 40000
  2. 0 <= A[i] <= 10^9

Solutions

Solution  ( 15ms)

class Solution {
  public int maxTurbulenceSize(int[] A) {
    int length = A.length;
    if (length == 1) {
      return 1;
    } else if (length == 2) {
      return A[0] == A[1] ? 1 : 2;
    }
    
    int lastCOmpare = Integer.compare(A[0], A[1]);
    int presentCompare;
    int maxLength = 0;
    int curLength = lastCOmpare == 0 ? 1 : 2;
    for (int i = 1, len = length - 1; i < len; i++) {
      presentCompare = Integer.compare(A[i], A[i+1]);
      if (lastCOmpare == 0) {
        lastCOmpare = presentCompare;
        curLength = lastCOmpare == 0 ? 1 : 2;
        continue;
      } else if (presentCompare == 0) {
        lastCOmpare = presentCompare;
        if (curLength > maxLength) {
          maxLength = curLength;
        }
        curLength = 1;
      } else if (Math.abs(presentCompare + lastCOmpare) == 2) {
        lastCOmpare = presentCompare;
        if (curLength > maxLength) {
          maxLength = curLength;
        }
        curLength = 2;
      } else {
        lastCOmpare = presentCompare;
        curLength++;
      }
    }
    if (curLength > maxLength) {
          maxLength = curLength;
    }
    return maxLength;
  }
}

Solution  ( 22ms)

class Solution {
    public int maxTurbulenceSize(int[] A) {
        int N = A.length;
        int ans = 1;
        int anchor = 0;

        for (int i = 1; i < N; ++i) {
            int c = Integer.compare(A[i-1], A[i]);
            if (i == N-1 || c * Integer.compare(A[i], A[i+1]) != -1) {
                if (c != 0) ans = Math.max(ans, i - anchor + 1);
                anchor = i;
            }
        }

        return ans;
    }
}

Solution (11ms)

class Solution {
    public int maxTurbulenceSize(int[] A) {
        if (A.length == 1)
            return 1;
        int[] o = new int[A.length-1];
        for (int i = 0; i < A.length - 1; ++i) {
            if (A[i + 1] - A[i] > 0) {
                o[i]=1;
            } else if (A[i + 1] - A[i] < 0) {
                o[i]=-1;
            } else {
                o[i]=0;
            }
        }
        int count=0;
        int maxCount=0;
       for(int i=0;i<o.length-1;++i)
        {
            if(o[i]*o[i+1]==-1)
            {
                count++;
                if(maxCount<count)
                    maxCount=count;
            }else{
                count=0;
            }
        }
        return maxCount+2;
    }
}

Notes

方法一:滑动窗口

思路

显然,我们只需要关注相邻两个数字之间的符号就可以了。 如果用 -1, 0, 1 代表比较符的话(分别对应 <、 =、 >),那么我们的目标就是在符号序列中找到一个最长的元素交替子序列 1, -1, 1, -1, ...(从 1 或者 -1 开始都可以)。

这些交替的比较符会形成若干个连续的块 。我们知道何时一个块会结束:当已经到符号序列末尾的时候或者当序列元素不再交替的时候。

举一个例子,假设给定数组为 A = [9,4,2,10,7,8,8,1,9]。那么符号序列就是 [1,1,-1,1,-1,0,-1,1]。它可以被划分成的块为 [1], [1,-1,1,-1], [0], [-1,1]

算法

从左往右扫描这个数组,如果我们扫描到了一个块的末尾(不再交替或者符号序列已经结束),那么就记录下这个块的答案并将其作为一个候选答案,然后设置下一个元素(如果有的话)为下一个块的开头。