C语言重构【978】最长湍流子数组

古城微笑少年丶 2023-01-08 02:30 121阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

当 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 <= A.length <= 40000
    0 <= A[i] <= 10^9

#### 方案： ####

*  使用一个变量res记录最大值、一个变量记录当前记录（的下一个）的长度
 *  根据题目的提示，分为两种情况，用type来标记
 *  当不满足当前type时需要转变type，此时需要覆盖最大值res、重置now为2（因为此时相当于判定另一种成功一次，则长度设为2）
 *  需要注意的是当前后出现相等的情况时，不属于两种情况之中，故需要初始化now为1

class Solution
    { 
    public:
        int maxTurbulenceSize(vector<int> &arr)
        { 
            //now表示当前最长
            int res = 1, now = 1, type = 1;
            int len = arr.size();
    
            for (int i = 0; i < len - 1; i++)
            {    
                //当相等的时候应当断掉，并跳过这个元素
                if(arr[i]==arr[i+1]){ 
                    res = max(res, now);
                    now = 1;
                }
                //模式1=情况1
                else if (type == 1)
                { 
                    if ((i % 2 == 0 && arr[i] < arr[i + 1]) || (i % 2 == 1 && arr[i] > arr[i + 1]))
                    { 
                        now++;
                    }
                    else if ((i % 2 == 0 && arr[i] > arr[i + 1]) || (i % 2 == 1 && arr[i] < arr[i + 1]))
                    { 
                        res = max(res, now);
                        now = 2;
                        type = 0;
                    }
                }
                //模式2=情况2
                else if (type == 0)
                { 
                    if ((i % 2 == 0 && arr[i] < arr[i + 1]) || (i % 2 == 1 && arr[i] > arr[i + 1]))
                    { 
                        res = max(res, now);
                        now = 2;
                        type = 1;
                    }
                    else if ((i % 2 == 0 && arr[i] > arr[i + 1]) || (i % 2 == 1 && arr[i] < arr[i + 1]))
                    { 
                        now++;
                    }
                }
            }
            return res > now ? res : now;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode