力扣2760 C++滑动窗口解法

问题分析

题目要求：给定一个整数数组nums和一个整数threshold，寻找最长的奇偶子数组。子数组需满足以下条件：

1. 子数组的第一个元素是偶数。
2. 子数组中的元素奇偶性交替（即nums[i] % 2 != nums[i+1] % 2）。
3. 子数组中的每个元素都不大于threshold。

核心约束在于，子数组必须同时满足奇偶性交替和元素值上限两个条件。一旦某个元素不满足任一条件，当前子数组的连续性即被破坏，需要从新的位置开始寻找。

算法设计

1. 滑动窗口 (双指针)

这是最直观且高效的解法。使用两个指针left和right来定义当前考察的子数组窗口[left, right]。我们不断尝试扩展右边界right，并在每次扩展后检查新加入的元素nums[right]是否破坏了子数组的合法性。如果破坏，则收缩左边界left至right的位置，并重新开始构建窗口。

关键点：

• 合法性检查：对于窗口[left, right]，需要检查nums[right]是否满足：
  1. nums[right] <= threshold
  2. 如果right == left，则它是窗口的第一个元素，必须是偶数。
  3. 如果right > left，则nums[right]的奇偶性必须与nums[right-1]相反。
• 窗口维护：当nums[right]合法时，扩展窗口 (right++)；不合法时，将窗口重置 (left = right, right = left)，但需注意如果nums[right]本身不满足条件1，则left和right都应跳到下一位 (left = right + 1, right = left)。

2. 模拟 (一次遍历)

滑动窗口的变体，可以简化为一次遍历。我们维护一个当前有效子数组的长度currentLength和全局最大长度maxLength。遍历数组，根据当前元素nums[i]与上一个元素nums[i-1]的关系以及阈值条件，决定是延续当前子数组还是开始一个新的子数组。

状态判断逻辑：

1. 如果nums[i] > threshold，当前元素绝对非法，currentLength重置为0。
2. 否则，如果currentLength == 0，说明我们正在尝试开始一个新的子数组。此时需要nums[i] % 2 == 0才能成功开始，currentLength = 1；否则保持为0。
3. 否则 (currentLength > 0)，说明我们处于一个有效的子数组中。此时需要检查奇偶交替条件：nums[i] % 2 != nums[i-1] % 2。如果满足，currentLength++；否则，说明奇偶性没有交替，但nums[i]本身可能可以作为下一个子数组的起点（如果它是偶数），因此currentLength应重置为(nums[i] % 2 == 0) ? 1 : 0。

C++ 代码实现

方案一：滑动窗口 (双指针)

class Solution { public: int longestAlternatingSubarray(vector<int>& nums, int threshold) { int n = nums.size(); int maxLen = 0; int left = 0, right = 0; while (right < n) { // 条件1：元素值不超过阈值 if (nums[right] > threshold) { // 当前元素非法，左右指针都跳到下一个位置 left = right + 1; right = left; continue; } // 条件2 & 3：奇偶性检查 if (right == left) { // 子数组第一个元素必须是偶数 if (nums[right] % 2 != 0) { left = right + 1; right = left; continue; } } else { // 后续元素必须奇偶交替 if (nums[right] % 2 == nums[right - 1] % 2) { // 不满足交替，从right开始新的窗口 left = right; // right指针不动，下一轮循环会以right为left重新判断 continue; } } // 当前窗口 [left, right] 合法，更新最大长度 maxLen = max(maxLen, right - left + 1); right++; // 尝试扩展右边界 } return maxLen; } };

代码解析：

• left和right指针初始化为0。
• 外层while循环控制右指针right遍历数组。
• 内部分三步检查合法性：
  1. 首先检查阈值条件nums[right] > threshold。如果违反，则left和right都移动到right+1，彻底跳过这个非法元素 。
  2. 然后检查是否是窗口起点 (right == left)。如果是，则要求nums[right]为偶数，否则重置窗口 。
  3. 最后检查奇偶交替性 (nums[right] % 2 == nums[right-1] % 2)。如果相同，说明交替性被破坏，将left移动到right，准备以当前位置为起点构建新窗口 。
• 只有当所有条件都满足时，才计算当前窗口长度并更新maxLen，然后right++继续扩展。

方案二：模拟 (一次遍历)

class Solution { public: int longestAlternatingSubarray(vector<int>& nums, int threshold) { int maxLen = 0; int currentLen = 0; int n = nums.size(); for (int i = 0; i < n; ++i) { if (nums[i] > threshold) { // 违反阈值条件，当前子数组终结 currentLen = 0; } else if (currentLen == 0) { // 尝试开始一个新的子数组，首元素必须为偶数 currentLen = (nums[i] % 2 == 0) ? 1 : 0; } else { // 已在子数组中，检查奇偶是否交替 if (nums[i] % 2 != nums[i - 1] % 2) { currentLen++; } else { // 没有交替，当前元素可能作为新子数组的起点 currentLen = (nums[i] % 2 == 0) ? 1 : 0; } } maxLen = max(maxLen, currentLen); } return maxLen; } };

代码解析：

• currentLen记录以当前位置i结尾的、满足条件的最长子数组长度。
• maxLen记录全局最大值。
• 遍历中的三个分支对应三种状态：
  1. 元素值超标：直接清零currentLen，因为任何包含该元素的子数组都不合法 。
  2. 当前无有效子数组(currentLen == 0)：尝试以nums[i]作为新起点。只有当它是偶数时，才能成功开启一个长度为1的子数组 。
  3. 已有有效子数组(currentLen > 0)：检查奇偶交替性。如果交替，长度加1；如果不交替，说明连续性中断。但nums[i]本身如果为偶数，它可以立即作为下一个子数组的起点（长度为1），否则长度归零 。
• 每次循环后更新maxLen。

复杂度与方案对比

示例演示

以nums = [3, 2, 5, 4],threshold = 5为例，演示模拟法的过程：

最终找到的最长子数组为[2, 5, 4]，长度为3 。

参考来源

• ​LeetCode解法汇总2760. 最长奇偶子数组
• Leetcode—2760.最长奇偶子数组【简单】
• LeetCode 2760. 最长奇偶子数组：模拟（使用一个变量记录状态）
• 2760. 最长奇偶子数组 : 抽丝剥茧，图解双指针做法正确性
• leetcode做题笔记2760. 最长奇偶子数组
• 【每日一题】 2024年1月汇编