C++描述 LeetCode 978. 最長湍流子數組

  

  大家好，我叫亓官劼（qí guān jié ）

當 ​

​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​

​ 的最大湍流子數組的長度。

示例 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​

   ​

解題思路

• 如果左右指針相同，即指向同一個位置時，如果目前數和下一個一樣，則一起右移，如果不同，則右指針移動，左指針不動，目前兩個數是滿足的。
• 如果左右指針不同，目前右指針數比左右兩個都小，或者比左右兩個都大，則右移，否則重置左指針

算法實作

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int len = arr.size(), res = 1, left = 0, right = 0;
        while (right < len - 1) {
            if (left == right) {
                // 左右指針相同時，如果目前數和下一個一樣，則一起右移，如果不同，則右指針移動，左指針不動，目前兩個數是滿足的
                if (arr[left] == arr[left + 1]) {
                    left++;
                }
                right++;
            } else {
                // 如果目前右指針數比左右兩個都小，或者比左右兩個都大，則右移，否則重置左指針
                if (arr[right - 1] < arr[right] && arr[right] > arr[right + 1]) {
                    right++;
                } else if (arr[right - 1] > arr[right] && arr[right] < arr[right + 1]) {
                    right++;
                } else {
                    left = right;
                }
            }
            res = max(res, right - left + 1);
        }
        return res;
    }
};