最长奇偶子数组
难度:
标签:
题目描述
You are given a 0-indexed integer array nums and an integer threshold.
Find the length of the longest subarray of nums starting at index l and ending at index r (0 <= l <= r < nums.length) that satisfies the following conditions:
nums[l] % 2 == 0- For all indices
iin the range[l, r - 1],nums[i] % 2 != nums[i + 1] % 2 - For all indices
iin the range[l, r],nums[i] <= threshold
Return an integer denoting the length of the longest such subarray.
Note: A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [3,2,5,4], threshold = 5 Output: 3 Explanation: In this example, we can select the subarray that starts at l = 1 and ends at r = 3 => [2,5,4]. This subarray satisfies the conditions. Hence, the answer is the length of the subarray, 3. We can show that 3 is the maximum possible achievable length.
Example 2:
Input: nums = [1,2], threshold = 2 Output: 1 Explanation: In this example, we can select the subarray that starts at l = 1 and ends at r = 1 => [2]. It satisfies all the conditions and we can show that 1 is the maximum possible achievable length.
Example 3:
Input: nums = [2,3,4,5], threshold = 4 Output: 3 Explanation: In this example, we can select the subarray that starts at l = 0 and ends at r = 2 => [2,3,4]. It satisfies all the conditions. Hence, the answer is the length of the subarray, 3. We can show that 3 is the maximum possible achievable length.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 1001 <= threshold <= 100
代码结果
运行时间: 69 ms, 内存: 16.1 MB
/*
* 题目思路：
* 1. 使用Java Stream进行数据流处理，完成与Java代码相同的逻辑。
* 2. 使用IntStream来进行数组元素的遍历和过滤。
*/
import java.util.stream.IntStream;
public class SolutionStream {
public int longestValidSubarray(int[] nums, int threshold) {
return IntStream.range(0, nums.length)
.filter(i -> nums[i] % 2 == 0)
.map(l -> {
int maxLength = 0;
int r = l;
int prevParity = nums[r] % 2;
while (r < nums.length && nums[r] <= threshold) {
int currentParity = nums[r] % 2;
if (currentParity == prevParity && r != l) {
break;
}
prevParity = currentParity;
r++;
}
return r - l;
})
.max()
.orElse(0);
}
}解释
方法:
本题解通过遍历数组来查找符合条件的最长子数组。首先从数组的第一个元素开始，检查每个元素是否为偶数且小于等于阈值。如果满足条件，这个元素可以作为子数组的起点。然后从这个起点开始，继续检查后续的元素，要求它们必须交替为奇数和偶数，且也要小于等于阈值，直到不满足条件为止。每次都记录并更新最长的子数组长度。如果遇到的元素不符合做为起点的条件，就将起点向后移动一位，继续检查。
时间复杂度:
O(n^2)
空间复杂度:
O(1)
代码细节讲解
🦆
在题解中，如何确保每次更新的起点`l`都是偶数且满足不超过阈值的条件？
▷🦆
算法在遇到不符合条件的元素时是如何调整起点`l`的？请详细说明其逻辑。
▷🦆
为什么在遇到当前元素超过阈值或与前一个元素奇偶性相同的情况下会停止扩展子数组？
▷🦆
在处理边界情况，如数组中所有元素都符合条件或完全不符合条件时，题解的处理策略是什么？
▷