2024年1月23日每日一题--2765. 最长交替子数组

2765. 最长交替子数组

题目分析

注： 其按照原始数组的排序进行判断，不能打乱原始的顺序。

所以，为此需要有一个标志位用于判断当前的趋势，所以使用flag作为标志位，为0表示当前无趋势，为1时，下一次为向上的趋势，为-1时，下一次为向下的趋势。

方案一

class Solution {
    public int alternatingSubarray(int[] nums) {

        int result = -1;
        int tempResult = -1;
        int flag = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            if (flag == 1) {
                if (nums[i] == nums[i + 1] + 1) {
                    flag = -1;
                    tempResult++;
                } else {
                    i--;
                    flag = 0;
                    result = Math.max(result, tempResult);
                }
            } else if (flag == -1) {
                if (nums[i] == nums[i + 1] - 1) {
                    flag = 1;
                    tempResult++;
                } else {
                    i--;
                    flag = 0;
                    result = Math.max(result, tempResult);
                }
            } else {
                if (nums[i] == nums[i + 1] - 1) {
                    flag = 1;
                    tempResult = 2;
                } else if (nums[i] == nums[i + 1] - 1) {
                    flag = -1;
                    tempResult = 2;
                }
            }
        }

        result = Math.max(result, tempResult);

        return result;
    }
}

结果

解答成功:
执行耗时:1 ms,击败了100.00% 的Java用户
内存消耗:43.2 MB,击败了23.95% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

官方题解

https://leetcode.cn/problems/longest-alternating-subarray/solutions/

class Solution {
    public int alternatingSubarray(int[] nums) {
        int res = -1;
        int n = nums.length;
        for (int firstIndex = 0; firstIndex < n; firstIndex++) {
            for (int i = firstIndex + 1; i < n; i++) {
                int length = i - firstIndex + 1;
                if (nums[i] - nums[firstIndex] == (length - 1) % 2) {
                    res = Math.max(res, length);
                } else {
                    break;
                }
            }
        }
        return res;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/longest-alternating-subarray/solutions/2610815/zui-chang-jiao-ti-zi-xu-lie-by-leetcode-2aevc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public int alternatingSubarray(int[] nums) {
        int n = nums.length;
        int max = -1;
        int idx = 0;
        for (int i = 1; i < n; i++) {
            int len = i - idx + 1;
            //子数组是否符合交替
            //交替子数组内,idx相差为偶数时差值为0(s2-s0=0),否则差值为1(s1-s0=1).
            if (nums[i] - nums[idx] == (len - 1) % 2) {
                max = Math.max(max, len);
            }
            //当前非子数组内,计算新子数组起始位置
            else {
                //当前相比i-1 符合交替,从i-1 开始计算新子数组,否则i
                if (nums[i] - nums[i - 1] == 1) {
                    idx = i - 1;
                    max = Math.max(max, 2);
                } else {
                    idx = i;
                }
            }
        }
        return max;
    }
}