题目描述
给你一个下标从 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
解释:交替子数组有 [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
解法
方法一:枚举
我们可以枚举子数组的左端点 $i$,对于每个 $i$,我们需要找到最长的满足条件的子数组。我们可以从 $i$ 开始向右遍历,每次遇到相邻元素差值不满足交替条件时,我们就找到了一个满足条件的子数组。我们可以用一个变量 $k$ 来记录当前元素的差值应该是 $1$ 还是 $-1$,如果当前元素的差值应该是 $-k$,那么我们就将 $k$ 取反。当我们找到一个满足条件的子数组 $nums[i..j]$ 时,我们更新答案为 $\max(ans, j - i + 1)$。
时间复杂度 $O(n^2)$,其中 $n$ 是数组的长度。我们需要枚举子数组的左端点 $i$,对于每个 $i$,我们需要 $O(n)$ 的时间来找到最长的满足条件的子数组。空间复杂度 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def alternatingSubarray(self, nums: List[int]) -> int:
ans, n = -1, len(nums)
for i in range(n):
k = 1
j = i
while j + 1 < n and nums[j + 1] - nums[j] == k:
j += 1
k *= -1
if j - i + 1 > 1:
ans = max(ans, j - i + 1)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public int alternatingSubarray(int[] nums) {
int ans = -1, n = nums.length;
for (int i = 0; i < n; ++i) {
int k = 1;
int j = i;
for (; j + 1 < n && nums[j + 1] - nums[j] == k; ++j) {
k *= -1;
}
if (j - i + 1 > 1) {
ans = Math.max(ans, j - i + 1);
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution {
public:
int alternatingSubarray(vector<int>& nums) {
int ans = -1, n = nums.size();
for (int i = 0; i < n; ++i) {
int k = 1;
int j = i;
for (; j + 1 < n && nums[j + 1] - nums[j] == k; ++j) {
k *= -1;
}
if (j - i + 1 > 1) {
ans = max(ans, j - i + 1);
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | func alternatingSubarray(nums []int) int {
ans, n := -1, len(nums)
for i := range nums {
k := 1
j := i
for ; j+1 < n && nums[j+1]-nums[j] == k; j++ {
k *= -1
}
if t := j - i + 1; t > 1 && ans < t {
ans = t
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | function alternatingSubarray(nums: number[]): number {
let ans = -1;
const n = nums.length;
for (let i = 0; i < n; ++i) {
let k = 1;
let j = i;
for (; j + 1 < n && nums[j + 1] - nums[j] === k; ++j) {
k *= -1;
}
if (j - i + 1 > 1) {
ans = Math.max(ans, j - i + 1);
}
}
return ans;
}
|