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

解题思路

这道题要求找到满足三个条件的最长子数组：

  1. 子数组必须以偶数开头
  2. 相邻元素必须奇偶性不同（交替出现）
  3. 所有元素都不超过阈值

由于数组长度最大只有100，可以使用暴力枚举的方法。对于每个可能作为起始位置的偶数元素，向右扩展子数组，检查是否满足条件。

解法思路：

  1. 遍历数组中的每个位置作为潜在的起始点
  2. 对于每个起始点，首先检查是否为偶数且不超过阈值
  3. 从起始点开始向右扩展，检查：
    • 当前元素是否不超过阈值
    • 相邻元素是否奇偶性不同
  4. 记录满足条件的最长子数组长度

由于数据规模较小，这种O(n²)的解法完全可以接受。对于每个有效的起始位置，我们尽可能地向右扩展，直到不满足条件为止，然后更新最大长度。

代码实现

class Solution {
public:
    int longestAlternatingSubarray(vector<int>& nums, int threshold) {
        int n = nums.size();
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            // 检查起始位置：必须是偶数且不超过阈值
            if (nums[i] % 2 == 0 && nums[i] <= threshold) {
                int len = 1;
                
                // 从当前位置向右扩展
                for (int j = i + 1; j < n; j++) {
                    // 检查当前元素是否超过阈值
                    if (nums[j] > threshold) break;
                    
                    // 检查相邻元素奇偶性是否不同
                    if (nums[j] % 2 == nums[j-1] % 2) break;
                    
                    len++;
                }
                
                maxLen = max(maxLen, len);
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def longestAlternatingSubarray(self, nums: List[int], threshold: int) -> int:
        n = len(nums)
        max_len = 0
        
        for i in range(n):
            # 检查起始位置：必须是偶数且不超过阈值
            if nums[i] % 2 == 0 and nums[i] <= threshold:
                length = 1
                
                # 从当前位置向右扩展
                for j in range(i + 1, n):
                    # 检查当前元素是否超过阈值
                    if nums[j] > threshold:
                        break
                    
                    # 检查相邻元素奇偶性是否不同
                    if nums[j] % 2 == nums[j-1] % 2:
                        break
                    
                    length += 1
                
                max_len = max(max_len, length)
        
        return max_len

public class Solution {
    public int LongestAlternatingSubarray(int[] nums, int threshold) {
        int n = nums.Length;
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            // 检查起始位置：必须是偶数且不超过阈值
            if (nums[i] % 2 == 0 && nums[i] <= threshold) {
                int len = 1;
                
                // 从当前位置向右扩展
                for (int j = i + 1; j < n; j++) {
                    // 检查当前元素是否超过阈值
                    if (nums[j] > threshold) break;
                    
                    // 检查相邻元素奇偶性是否不同
                    if (nums[j] % 2 == nums[j-1] % 2) break;
                    
                    len++;
                }
                
                maxLen = Math.Max(maxLen, len);
            }
        }
        
        return maxLen;
    }
}

var longestAlternatingSubarray = function(nums, threshold) {
    let maxLength = 0;
    
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] % 2 === 0 && nums[i] <= threshold) {
            let length = 1;
            
            for (let j = i + 1; j < nums.length; j++) {
                if (nums[j] <= threshold && nums[j] % 2 !== nums[j-1] % 2) {
                    length++;
                } else {
                    break;
                }
            }
            
            maxLength = Math.max(maxLength, length);
        }
    }
    
    return maxLength;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大O表示法说明
时间复杂度O(n²)外层循环遍历所有起始位置，内层循环扩展子数组，最坏情况下需要遍历整个数组
空间复杂度O(1)只使用了常数额外空间来存储变量