2765. 最长交替子数组

给你一个下标从 0 开始的整数数组 nums 。如果 nums 中长度为 m 的子数组 s 满足以下条件，我们称它是一个 交替子数组 ：

m 大于 1 。
s1 = s0 + 1 。
下标从 0 开始的子数组 s 与数组 [s0, s1, s0, s1,...,s(m-1) % 2] 一样。也就是说，s1 - s0 = 1 ，s2 - s1 = -1 ，s3 - s2 = 1 ，s4 - s3 = -1 ，以此类推，直到 s[m - 1] - s[m - 2] = (-1)m 。

请你返回 nums 中所有交替子数组中，最长的长度，如果不存在交替子数组，请你返回 -1 。

子数组是一个数组中一段连续非空的元素序列。

示例 1：

输入：nums = [2,3,4,3,4]

输出：4

解释：交替子数组有 [2,3]，[3,4]，[3,4,3] 和 [3,4,3,4]。最长的子数组为 [3,4,3,4]，长度为 4。

示例 2：

输入：nums = [4,5,6]

输出：2

解释：[4,5] 和 [5,6] 是仅有的两个交替子数组。它们长度都为 2 。

提示：

2 <= nums.length <= 100
1 <= nums[i] <= 104

思路

暴力模拟
滑动窗口+贪心策略

代码

暴力模拟

class Solution {
    public int alternatingSubarray(int[] nums) {
        int result = -1;
        boolean flag = false;
        int count = -1;
        int temp = -1;
        int a = 1;
        for (int i = 1; i < nums.length; i++) {
            if (flag) {
                if (temp == (i & 1)) {
                    a = 1;
                } else {
                    a = -1;
                }
                if (nums[i] - nums[i - 1] == a) {
                    count++;
                } else {
                    result = Math.max(result, count);
                    count = 2;
                    if (nums[i] - nums[i - 1] == 1) {
                        result = Math.max(result, 2);
                        temp = i & 1;
                    } else {
                        flag = false;
                    }
                }
            } else {
                if (nums[i] - nums[i - 1] == 1) {
                    result = Math.max(result, 2);
                    temp = i & 1;
                    count = 2;
                    flag = true;
                }
            }
        }
        result = Math.max(result, count);
        return result;
    }
}

最终简化版本：

class Solution {
    public int alternatingSubarray(int[] nums) {
        int result = -1;
        int count = -1;
        int temp = 1;
        for (int i = 1; i < nums.length; i++) {
            int differ = nums[i] - nums[i - 1];
            // 比较 temp , temp值在 1,-1转换，第一次temp = 1,即判断是否交替子数组开头
            if (differ == temp) {
                // 交替子数组开头，长度设置为2
                if (count == -1) {
                    count = 2;
                } else {
                    //不是交替子数组开头，进行累加操作
                    count++;
                }
            } else {
                //  不符合交替规则时，初始化计数字段为-1，避免differ不为1或-1时对计数的干扰
                count = -1;
                // 是 新交替子数组开头
                if (differ == 1) {
                    temp = 1; // 提前置换 temp = 1 ,下次比较时 temp = -1
                    count = 2;// 新开头就已经存在2位长度了(和第一次判断是否交替子数组开头同样的效果)
                } else {// 不是 新交替子数组开头
                    temp = -1;// 提前置换 temp = -1 ,下次比较时 temp = 1
                }
            }
            // 变成相反数：1 => -1 , -1 => 1
            temp = -temp;
            // 记录最大长度
            result = Math.max(result, count);
        }
        return result;
    }
}

滑动窗口+贪心策略

class Solution {
    public int alternatingSubarray(int[] nums) {
        int l = 0, r = 1, next = 1, ans = -1;
        while (r < nums.length) {
            int differ = nums[r] - nums[r - 1];
            //保证窗口内元素满足交替数组的条件
            if (differ != next) {
                l = differ == 1 ? r - 1 : r;
                next = differ == 1 ? 1 : -1;
            }
            next = -next;
            if (++r - l > 1) ans = Math.max(ans, r - l);
        }
        return ans;
    }
}