LeetCode.2765. 最长交替子数组

题目

2765. 最长交替子数组

分析

为了得到数组 nums 中的最长交替子数组的长度，需要分别计算以每个下标结尾的最长交替子数组的长度。为了方便处理，计算过程中需要考虑长度等于 1 的最长交替子数组，再返回结果时判断最长交替子数组的长度是否大于 1。

以下标 0 结尾的最长交替子数组的长度等于 1。对于 i>0 ，计算以下标 i 结尾的最长交替子数组的长度时需要考虑以下标 i-1 结尾的最长交替子数组的长度、当前相邻元素之差 curDiff = nums[i] - nums[i-1] 与上一个相邻元素之差 preDiff = nums[i-1]-nums[i-2]，分别考虑以下情况：

① 如果 preDiff * curDiff = -1，则可以将 nums[i] 添加到以 nums[i-1]结尾的最长交替子数组的末尾，使最长交替子数组的长度加 1，因此以下标 i 结尾的最长交替子数组的长度等于以下标 i-1 结尾的最长交替子数组的长度+1。

② 如果 preDiff * curDiff != -1 且 curDiff = 1，则以下标 i 结尾的最长交替子数组包含 nums[i-]和nums[i]，因此以下标 i 结尾的最长交替子数组的长度等于 2。

③ 如果 preDiff * curDiff != 1 且 curDiff !=1 ,则以下标 i 结尾的最长交替子数组包含 nums[i]，因此以下标 i 结尾的最长交替子数组的长度等于 1。

特别的，当 i=1 时，preDiff 不存在，因此一定不满足 preDiff * curDiff = -1，可以将 preDiff 初始化为一个绝对值大于 1 的整数。

遍历所有大于 0 的下标 i 之后，即可得到最长交替子数组的长度。如果最长交替子数组的长度大于 1，则返回最长交替子数组的长度，否则返回 -1。

代码

class Solution {
    public int alternatingSubarray(int[] nums) {
        int maxLength = -1;
        int curLength = 1;
        int preDiff = -2;
        int curDiff = 1;

        for(int i = 1;i < nums.length;i ++) {
            curDiff = nums[i] - nums[i - 1];
            if(preDiff * curDiff == -1) {
                curLength ++;
            }else if(curDiff == 1) {
                curLength = 2;
            }else {
                curLength = 1;
            }

            maxLength = Math.max(maxLength,curLength);
            preDiff = curDiff;
        }
        return maxLength > 1 ? maxLength : -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

参考

参考题解