class Solution {
public:
int longestAlternatingSubarray(vector<int>& nums, int threshold) {
}
};
6909. 最长奇偶子数组
给你一个下标从 0 开始的整数数组 nums 和一个整数 threshold 。
请你从 nums 的子数组中找出以下标 l 开头、下标 r 结尾 (0 <= l <= r < nums.length) 且满足以下条件的 最长子数组 ：
nums[l] % 2 == 0[l, r - 1] 内的所有下标 i ，nums[i] % 2 != nums[i + 1] % 2[l, r] 内的所有下标 i ，nums[i] <= threshold以整数形式返回满足题目要求的最长子数组的长度。
注意：子数组 是数组中的一个连续非空元素序列。
示例 1：
输入：nums = [3,2,5,4], threshold = 5 输出：3 解释：在这个示例中，我们选择从 l = 1 开始、到 r = 3 结束的子数组 => [2,5,4] ，满足上述条件。 因此，答案就是这个子数组的长度 3 。可以证明 3 是满足题目要求的最大长度。
示例 2：
输入：nums = [1,2], threshold = 2 输出：1 解释： 在这个示例中，我们选择从 l = 1 开始、到 r = 1 结束的子数组 => [2] 。 该子数组满足上述全部条件。可以证明 1 是满足题目要求的最大长度。
示例 3：
输入：nums = [2,3,4,5], threshold = 4 输出：3 解释： 在这个示例中，我们选择从 l = 0 开始、到 r = 2 结束的子数组 => [2,3,4] 。 该子数组满足上述全部条件。 因此，答案就是这个子数组的长度 3 。可以证明 3 是满足题目要求的最大长度。
提示：
1 <= nums.length <= 100 1 <= nums[i] <= 100 1 <= threshold <= 100原站题解
rust 解法, 执行用时: 8 ms, 内存消耗: 2.3 MB, 提交时间: 2023-11-16 00:06:42
impl Solution {
pub fn longest_alternating_subarray(nums: Vec<i32>, threshold: i32) -> i32 {
let mut ans = 0;
let mut i = 0;
let n = nums.len();
while i < n {
if nums[i] % 2 > 0 || nums[i] > threshold {
i += 1;
} else {
let j = i;
i += 1;
while i < n && nums[i] <= threshold && nums[i] % 2 != nums[i-1] % 2 {
i += 1;
}
ans = ans.max(i as i32 - j as i32);
}
}
ans
}
}
javascript 解法, 执行用时: 236 ms, 内存消耗: 48.4 MB, 提交时间: 2023-11-16 00:06:21
var isSatisfied = function(nums, l, r, threshold) {
if (nums[l] % 2 != 0) {
return false;
}
for (let i = l; i <= r; i++) {
if (nums[i] > threshold || (i < r && nums[i] % 2 == nums[i + 1] % 2)) {
return false;
}
}
return true;
};
/**
* @param {number[]} nums
* @param {number} threshold
* @return {number}
*/
var longestAlternatingSubarray = function(nums, threshold) {
let res = 0;
for (let l = 0; l < nums.length; l++) {
for (let r = 0; r < nums.length; r++) {
if (isSatisfied(nums, l, r, threshold)) {
res = Math.max(res, r - l + 1);
}
}
}
return res;
};
java 解法, 执行用时: 4 ms, 内存消耗: 42.4 MB, 提交时间: 2023-07-03 09:42:26
// 滑动窗口
class Solution {
public int longestAlternatingSubarray(int[] nums, int threshold) {
//最长子数组长度
int max = 0;
int l = 0;
int r = 0;
while(r < nums.length){
if(nums[l] % 2 != 0 || nums[l] > threshold){
l++;
r++;
continue;
}
//左边界满足时 更新max
max = Math.max(max,r-l+1);
//右指针到数组最后时 提前返回 以免移动指针越界
if(r == nums.length -1) return max;
//左边界满足 尝试移动右指针
r++;
//右指针的值超过阈值或者出现连续奇偶数 将左指针更新成r
if(nums[r-1] % 2 == nums[r] % 2 || nums[r] > threshold){
l = r;
continue;
}
//如果右指针移动后正常 更新max
max = Math.max(max,r-l+1);
}
return max;
}
}
cpp 解法, 执行用时: 80 ms, 内存消耗: 88.9 MB, 提交时间: 2023-07-03 09:41:25
/**
* 一边遍历，一边扩展
* 通过双指针遍历，先确定子数组的开头元素，然后从这个元素的下一个位置，再进行遍历即可。
**/
class Solution {
public:
int longestAlternatingSubarray(vector<int>& nums, int threshold) {
int res = 0;
int l = 0; //记录子数组的起始位置
int r = 0; //记录子数组的终止位置
for (int i = 0; i < nums.size(); i++) {
if (nums[i] % 2 != 0 || nums[i] > threshold) continue;//如果起始结点为奇数，或者大于给定的数值，则跳过本层循环
l = i;//记录起始结点
r = i; //记录终止结点
for (int j = i + 1; j < nums.size(); j++) { //找到起始的偶数结点后，则从这个起点往后遍历
if (nums[j] <= threshold && nums[j - 1] % 2 != nums[j] % 2) {
r++; //不断更新终止位置
}else {
break; //说明找到一个不满足的数据，则退出循环，结束本次子数组长度的记录。注意这条代码，比赛时就是忘记退出循环，导致部分数据无法通过，因为r会在后面满足条件时继续更新。
}
}
res = max(r - l + 1, res); //不断更新子数组的长度，每次取最大值
}
return res;
}
};
golang 解法, 执行用时: 52 ms, 内存消耗: 6.9 MB, 提交时间: 2023-07-03 09:40:32
func longestAlternatingSubarray(a []int, threshold int) (ans int) {
for i, n := 0, len(a); i < n; {
if a[i]%2 > 0 || a[i] > threshold {
i++
} else {
i0 := i
for i++; i < n && a[i] <= threshold && a[i]%2 != a[i-1]%2; i++ {}
ans = max(ans, i-i0)
}
}
return
}
func max(a, b int) int { if b > a { return b }; return a }
python3 解法, 执行用时: 108 ms, 内存消耗: 16.1 MB, 提交时间: 2023-07-03 09:35:34
'''
分组循环
题目的约束实际上把数组划分成了若干段，每段都满足要求，且互不相交。
那么遍历一遍，计算每一段的长度，取最大值，即为答案。
'''
class Solution:
def longestAlternatingSubarray(self, a: List[int], threshold: int) -> int:
ans, i, n = 0, 0, len(a)
while i < n:
if a[i] % 2 or a[i] > threshold:
i += 1
else:
i0 = i
i += 1
while i < n and a[i] <= threshold and a[i] % 2 != a[i - 1] % 2:
i += 1 # i 是全局变量，二重循环 i+=1 至多执行 O(n) 次
ans = max(ans, i - i0)
return ans