最长奇偶子数组

难度: Easy

给你一个下标从 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

Submission

运行时间: 69 ms

内存: 16.1 MB

class Solution:
    def longestAlternatingSubarray(self, nums: List[int], threshold: int) -> int:
        n=len(nums)
        l=0
        ans=0
        while l<n:


            if nums[l]%2==0 and nums[l]<=threshold:
                r=l+1
                cur=nums[l]%2
                while r<n:
                    if nums[r]>threshold or nums[r]%2==cur:
                        break
                    cur,r=nums[r]%2,r+1 
              
                ans=max(ans,r-l)
                l=r
            else:
                l+=1
        return ans

Explain

本题解通过遍历数组来查找符合条件的最长子数组。首先从数组的第一个元素开始，检查每个元素是否为偶数且小于等于阈值。如果满足条件，这个元素可以作为子数组的起点。然后从这个起点开始，继续检查后续的元素，要求它们必须交替为奇数和偶数，且也要小于等于阈值，直到不满足条件为止。每次都记录并更新最长的子数组长度。如果遇到的元素不符合做为起点的条件，就将起点向后移动一位，继续检查。

时间复杂度: O(n^2)

空间复杂度: O(1)

class Solution:
    def longestAlternatingSubarray(self, nums: List[int], threshold: int) -> int:
        n = len(nums)  # 数组长度
        l = 0  # 初始化起点索引
        ans = 0  # 初始化最长子数组长度
        while l < n:  # 遍历数组

            # 检查当前起点是否为偶数且不超过阈值
            if nums[l] % 2 == 0 and nums[l] <= threshold:
                r = l + 1  # 初始化终点索引
                cur = nums[l] % 2  # 初始化当前奇偶性
                while r < n:  # 尝试扩展子数组
                    # 如果当前元素超过阈值或与前一个元素奇偶性相同，则停止扩展
                    if nums[r] > threshold or nums[r] % 2 == cur:
                        break
                    cur, r = nums[r] % 2, r + 1  # 更新当前奇偶性并移动终点索引
                
                ans = max(ans, r - l)  # 更新最长子数组长度
                l = r  # 将起点移动到终点位置
            else:
                l += 1  # 移动起点索引
        return ans  # 返回最长子数组长度

Explore

在题解中，算法通过在while循环内部检查每个潜在的起点`l`是否为偶数且小于等于阈值来确保这一条件。如果`nums[l] % 2 == 0`（即`l`指向的元素是偶数）并且`nums[l] <= threshold`（即该元素值不超过给定的阈值），则`l`可以作为子数组的起点。如果这个条件不成立，算法会将`l`增加1，继续向后寻找直到找到满足条件的偶数且不超过阈值的新起点。

在算法中，如果当前检查的起点`l`不满足偶数且小于等于阈值的条件，或者在扩展子数组过程中遇到了不满足条件的元素（例如元素超过阈值或元素的奇偶性与前一个元素相同），起点`l`会被调整。具体来说，如果是在子数组扩展过程中遇到不符合条件的元素，则`l`会被更新为当前的终点`r`，因为此时`r`指向的是第一个不满足条件的元素。如果是在检查起点时就不满足条件，`l`会直接增加1，继续向后寻找可能的新起点。

子数组需要满足所有元素交替为奇数和偶数，且每个元素都必须小于等于阈值。如果当前元素超过阈值，那么它不满足子数组的条件。同样，如果当前元素与前一个元素的奇偶性相同，也违反了交替的规则。这两种情况都会导致当前子数组不再有效，因此需要停止扩展，并尝试从下一个可能的起点重新开始寻找新的子数组。

如果数组中所有元素都符合条件，算法将成功地扩展子数组直到数组的末尾，此时可以得到最大的子数组长度。如果没有任何元素符合作为起点的条件（偶数且小于等于阈值），则起点`l`将一直被递增直到数组末尾，最终返回的最长子数组长度将是0。这种方式确保了算法能够处理所有元素均符合或不符合条件的边界情况。