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;}
}

参考

参考题解