class Solution {
public:
int alternatingSubarray(vector<int>& nums) {
}
};
2765. 最长交替子序列
给你一个下标从 0 开始的整数数组 nums 。如果 nums 中长度为 m 的子数组 s 满足以下条件，我们称它是一个交替子序列：
m 大于 1 。s1 = s0 + 1 。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 <= 1001 <= nums[i] <= 104原站题解
rust 解法, 执行用时: 3 ms, 内存消耗: 2.2 MB, 提交时间: 2024-01-23 15:04:42
impl Solution {
pub fn alternating_subarray(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut ans = -1;
let mut i = 0;
while i < n - 1 {
if nums[i + 1] - nums[i] != 1 {
i += 1; // 直接跳过
continue;
}
let i0 = i; // 记录这一组的开始位置
i += 2; // i 和 i+1 已经满足要求，从 i+2 开始判断
while i < n && nums[i] == nums[i - 2] {
i += 1;
}
// 从 i0 到 i-1 是满足题目要求的（并且无法再延长的）子数组
ans = ans.max((i - i0) as i32);
i -= 1;
}
ans
}
}
javascript 解法, 执行用时: 95 ms, 内存消耗: 53.6 MB, 提交时间: 2024-01-23 15:04:25
/**
* @param {number[]} nums
* @return {number}
*/
var alternatingSubarray = function(nums) {
const n = nums.length;
let ans = -1, i = 0;
while (i < n - 1) {
if (nums[i + 1] - nums[i] !== 1) {
i++; // 直接跳过
continue;
}
const i0 = i; // 记录这一组的开始位置
i += 2; // i 和 i+1 已经满足要求，从 i+2 开始判断
while (i < n && nums[i] === nums[i - 2]) {
i++;
}
// 从 i0 到 i-1 是满足题目要求的（并且无法再延长的）子数组
ans = Math.max(ans, i - i0);
i--;
}
return ans;
};
cpp 解法, 执行用时: 18 ms, 内存消耗: 67.6 MB, 提交时间: 2024-01-23 15:04:08
class Solution {
public:
int alternatingSubarray(vector<int> &nums) {
int ans = -1;
int i = 0, n = nums.size();
while (i < n - 1) {
if (nums[i + 1] - nums[i] != 1) {
i++; // 直接跳过
continue;
}
int i0 = i; // 记录这一组的开始位置
i += 2; // i 和 i+1 已经满足要求，从 i+2 开始判断
while (i < n && nums[i] == nums[i - 2]) {
i++;
}
// 从 i0 到 i-1 是满足题目要求的（并且无法再延长的）子数组
ans = max(ans, i - i0);
i--;
}
return ans;
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 42.3 MB, 提交时间: 2023-07-10 09:23:02
class Solution {
public int alternatingSubarray(int[] nums) {
int res = 0;
int dp = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] - nums[i - 1] == 1) {
if (i >= 2 && nums[i - 1] - nums[i - 2] == -1 && dp > 0) {
dp += 1;
} else {
dp = 2;
}
} else if (nums[i] - nums[i - 1] == -1) {
if (i >= 2 && nums[i - 1] - nums[i - 2] == 1) {
dp += 1;
} else {
dp = 0;
}
}
res = Math.max(res, dp);
}
return res == 0 ? -1 : res;
}
}
golang 解法, 执行用时: 16 ms, 内存消耗: 4.1 MB, 提交时间: 2023-07-10 09:19:57
// 分组循环
func alternatingSubarray(nums []int) int {
ans := -1
for i, n := 0, len(nums); i < n-1; {
if nums[i+1]-nums[i] != 1 {
i++
continue
}
st := i
for i++; i < n && nums[i] == nums[st]+(i-st)%2; i++ {}
ans = max(ans, i-st)
i--
}
return ans
}
func max(a, b int) int { if b > a { return b }; return a }
python3 解法, 执行用时: 40 ms, 内存消耗: 16.1 MB, 提交时间: 2023-07-10 09:19:07
class Solution:
def alternatingSubarray(self, nums: List[int]) -> int:
ans = -1
i, n = 0, len(nums)
while i < n - 1:
if nums[i + 1] - nums[i] != 1:
i += 1
continue
i0 = i
i += 1
while i < n and nums[i] == nums[i0] + (i - i0) % 2:
i += 1
ans = max(ans, i - i0)
i -= 1
return ans