最长交替子数组
难度:
标签:
题目描述
You are given a 0-indexed integer array nums. A subarray s of length m is called alternating if:
mis greater than1.s1 = s0 + 1.- The 0-indexed subarray
slooks like[s0, s1, s0, s1,...,s(m-1) % 2]. In other words,s1 - s0 = 1,s2 - s1 = -1,s3 - s2 = 1,s4 - s3 = -1, and so on up tos[m - 1] - s[m - 2] = (-1)m.
Return the maximum length of all alternating subarrays present in nums or -1 if no such subarray exists.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [2,3,4,3,4] Output: 4 Explanation: The alternating subarrays are [3,4], [3,4,3], and [3,4,3,4]. The longest of these is [3,4,3,4], which is of length 4.
Example 2:
Input: nums = [4,5,6] Output: 2 Explanation: [4,5] and [5,6] are the only two alternating subarrays. They are both of length 2.
Constraints:
2 <= nums.length <= 1001 <= nums[i] <= 104
代码结果
运行时间: 22 ms, 内存: 16.1 MB
/*
思路：
1. 使用Java Stream API遍历数组，检查每个长度大于1的子数组是否为交替子数组。
2. 如果当前子数组满足交替子数组的条件，则更新最长交替子数组的长度。
3. 返回最长的交替子数组的长度，如果不存在则返回-1。
*/
import java.util.stream.IntStream;
public class Solution {
public int longestAlternatingSubarray(int[] nums) {
return IntStream.range(0, nums.length - 1)
.map(i -> {
int length = 1;
boolean isAlternating = true;
for (int j = i; j < nums.length - 1; j++) {
if ((j - i) % 2 == 0 && nums[j + 1] != nums[j] + 1) {
isAlternating = false;
break;
}
if ((j - i) % 2 == 1 && nums[j + 1] != nums[j] - 1) {
isAlternating = false;
break;
}
length++;
}
return isAlternating && length > 1 ? length : -1;
})
.max()
.orElse(-1);
}
}解释
方法:
该题解采用双指针策略来检测并统计最长的交替子数组。首先初始化两个指针a和b，分别代表交替子数组的当前两个连续元素。变量cnt用于记录当前交替子数组的长度，而max_cnt用于记录遇到的最长交替子数组的长度。接下来，遍历数组中的每个元素，检查当前元素是否能延续当前的交替模式。如果可以，则更新a，b和cnt。如果不可以，就将当前的cnt与max_cnt比较，更新max_cnt，并尝试重新开始一个新的交替子数组。循环结束后，再次比较cnt和max_cnt确保最后一个可能的子数组被正确处理。如果max_cnt仍为0，说明没有找到合适的交替子数组，返回-1。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在双指针策略中，a和b指针的具体作用是什么？它们是如何帮助识别和扩展交替子数组的？
▷🦆
题解中提到如果当前元素x能继续交替模式，则会更新a和b的值。请问在什么情况下x被认为是能继续当前的交替模式？
▷🦆
当检测到当前元素x不能继续交替模式时，代码进行了哪些操作来尝试重新开始一个新的交替子数组？这种方法是否能够确保不遗漏任何可能的交替子数组？
▷🦆
如果数组中的数字都是相同的，例如nums = [5, 5, 5, 5]，该算法会返回什么结果？算法对这种情况的处理是否合理？
▷