欢乐狗 发表于 2025-1-4 09:17:24

# LeetCode 2760: 最长奇偶子数组

LeetCode 2760: 最长奇偶子数组

问题形貌

给定一个整数数组 nums 和一个整数 threshold，你必要从 nums 的子数组中找出最长的符合以下条件的子数组&#xff1
a;


[*]子数组的第一个元素是偶数，且小于等于 threshold。
[*]子数组内的元素瓜代出现，即相邻元素的奇偶性差别。
[*]子数组中的每个元素都必须小于等于 threshold。
请返回满意上述条件的最宗子数组的长度。
示例

[size=3

]示例 1


输入&#xff1
a;
nums &#61
; [3

, 2, 5, 4]
threshold &#61
; 5
输出&#xff1
a;
3

解释&#xff1
a;
选择从 l &#61
; 1
到 r &#61
; 3

的子数组 ，满意所有条件&#xff1
a;


[*]2 是偶数，符合第一个条件&#xff1
b;
[*]2 和 5 是瓜代奇偶，符合第二个条件&#xff1
b;
[*]2, 5, 4 都小于等于 threshold。
因此，最长的满意条件的子数组长度为 3

。
[size=3

]示例 2

输入&#xff1
a;
nums &#61
; [1
, 2]
threshold &#61
; 2
输出&#xff1
a;
1
解释&#xff1
a;
选择子数组 ，它满意所有条件&#xff1
a;


[*]2 是偶数&#xff1
b;
[*]子数组只有一个元素，没有瓜代的要求&#xff1
b;
[*]2 小于等于 threshold。
因此，最宗子数组的长度为 1
。
[size=3

]示例 3



输入&#xff1
a;
nums &#61
; [2, 3

, 4, 5]threshold &#61
; 4 输出&#xff1
a;
3

解释&#xff1
a;
选择从 l &#61
; 0 到 r &#61
; 2 的子数组 [2, 3

, 4]，满意所有条件&#xff1
a;


[*]2 是偶数&#xff1
b;
[*]2 和 3

瓜代奇偶，3

和 4 瓜代奇偶&#xff1
b;
[*]2, 3

, 4 都小于等于 threshold。
因此，最宗子数组的长度为 3

。
思路分析

我们可以使用 双指针法 来办理这个问题。
[size=3

]步骤&#xff1
a;

[list=1
]
[*]外层循环&#xff1
a;从数组的每个偶数开始，作为埋伏的子数组的出发点。
[*]内层循环&#xff1
a;从当前偶数开始，逐个检查后续的元素&#xff1
a;

[*]如果当前元素小于等于 threshold 且奇偶性瓜代，则继承扩展子数组&#xff1
b;
[*]如果出现不满意条件的元素，则竣事当前子数组的扩展。

[*]更新最大子数组长度&#xff1
a;在内层循环竣事后，更新最宗子数组的长度。
[size=3

]时间复杂度&#xff1
a;



[*]外层循环遍历 nums，时间复杂度为 O(n)。
[*]内层循环遍历每个埋伏子数组，最坏情况下每个元素会被遍历一次，总时间复杂度为 O(n²)。
由于 n 的最大值为 1
00，O(n²) 的复杂度是可以担当的。
代码实现

class Solution:    def longestAlternatingSubarray(self, nums: List, threshold: int) -> int:      res, n &#61
; 0, len(nums)      # 外层循环，遍历每个偶数且小于等于 threshold 的元素      for i in range(n):            if nums % 2 !&#61
; 0 or nums > threshold:               continue            else:                a &#61
; 1
# 子数组的初始长度为 1
                for j in range(i &#43

; 1
, n):                  # 判断是否是瓜代的子数组且小于等于 threshold                  if nums <&#61
; threshold and nums[j - 1
] % 2 !&#61
; nums % 2:                        a &#43

;&#61
; 1
                  else:                        break# 不满意条件，退出内层循环                res &#61
; max(res, a)# 更新最大长度      return res 解释



[*]外层循环&#xff1
a;我们从每一个偶数且小于等于 threshold 的元素开始，逐个考虑它作为子数组的出发点。
[*]内层循环&#xff1
a;对于每一个子数组，我们检查是否满意瓜代条件以及每个元素是否小于等于 threshold。如果满意条件，则继承扩展子数组&#xff1
b;否则，停止扩展。
[*]更新最大值&#xff1
a;每次竣事内层循环后，我们更新当前找到的最长瓜代子数组的长度。
边界情况

[list=1
]
[*] 数组只有一个元素&#xff1
a;

[*]如果该元素是偶数且小于等于 threshold，则返回 1
。
[*]如果该元素不符合条件，则返回 0。

[*] 所有元素都不满意条件&#xff1
a;

[*]如果没有任何偶数满意条件，返回 0。

[*] 数组元素全部类似&#xff1
a;

[*]如果所有元素都是偶数而且小于等于 threshold，且数组长度大于 1
，则返回 1
（因为没有瓜代的子数组）。

总结

本题的关键是使用双指针或滑动窗口来探求最长的瓜代子数组，保证每个元素符合条件并满意瓜代奇偶性。通过适当的内外层循环判断，可以高效地找到答案。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao1
23

.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页: [1]
查看完整版本: # LeetCode 2760: 最长奇偶子数组