题目描述

一个 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 最长混乱子数组的长度。

样例

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

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

输入：[100]
输出：1

注意

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

算法

(贪心) $O(n)$

1. 我们记录上一个相邻数对之间的比较符号。lastIndex 记录子数组的起始下标，lastSign 记录上一个数对之间的比较符号，初始时为 -1，表示任何比较符号都是合法的。
2. 如果遍历时，发现当前数对的比较符号和上一个相同，则说明不符合规则。此时我们应该更新答案，然后将 lastIndex 设为 i - 1，比较符号不变。
3. 如果发现当前数对两个数字相等，则需要更新答案，然后将 lastIndex 设为 i，比较符号设置为 -1。
4. 如果满足规则，则继续遍历下一个数字。
5. 最后，在返回答案前，还需要更新一次答案。

时间复杂度

• 每个数字仅遍历一次，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅使用了常数的空间。

C++ 代码

class Solution {
public:
    int maxTurbulenceSize(vector<int>& A) {
        int n = A.size(), ans = 1;
        int lastSign = -1, lastIndex = 0;
        for (int i = 1; i < n; i++) {
            if (A[i] == A[i - 1]) {
                ans = max(ans, i - lastIndex);
                lastIndex = i;
                lastSign = -1;
            }
            else {
                if (lastSign == -1) {
                    lastSign = (int)(A[i] > A[i - 1]);
                }
                else if (lastSign == (int)(A[i] > A[i - 1])) {
                    ans = max(ans, i - lastIndex);
                    lastIndex = i - 1;
                }
                else {
                    lastSign = 1 - lastSign;
                }
            }
        }
        ans = max(ans, n - lastIndex);
        return ans;
    }
};