【每日一题】最长奇偶子数组

文章目录

Tag
题目来源
解题思路
- 方法一：枚举
- 方法二：一次遍历
其他语言
- python3
写在最后

Tag

【一次遍历】【枚举】【数组】【2023-11-16】

题目来源

2760. 最长奇偶子数组

解题思路

方法一：枚举

本题有多种方法可以解决，最朴素的方法就是枚举所有的子数组，对枚举的所有子数组逐一判断是否是符合要求的奇偶数组，统计最大的奇偶数组长度即可。

该方法属于基础语法范畴，不再进行详细分析，具体请见代码。

实现代码

class Solution {
public:
    bool isValid(vector<int>& nums, int l , int r, int threshold) {
        if (nums[l] % 2 != 0) {
            return false;
        }
        for (int i = l; i <= r; ++i) {
            if (nums[i] > threshold || (i + 1 <= r && nums[i] % 2 == nums[i+1] % 2)) {
                return false;
            }
        }
        return true;
    }

    int longestAlternatingSubarray(vector<int>& nums, int threshold) {
        int n = nums.size();
        int res = 0;
        for (int l = 0; l < n; ++l) {
            for (int r = l; r < n; ++r) {
                if (isValid(nums, l, r, threshold)) {
                    res = max(res, r - l + 1);
                }
            }
        }
        return res;
    }
};

复杂度分析

时间复杂度： $O(n^3)$ ， $n$ 是数组 nums 的长度。

空间复杂度： $O (1)$ 。

方法二：一次遍历

本方法参考教你一次性把代码写对！O(n) 分组循环（Python/Java/C++/Go/JS/Rust）。

我们可以先找到有效的开始位置 i，再从有效的开始位置向后找最长的有效子数组的长度，该方法的时间复杂度为 $O (n)$ ，因为 i 是一直增加的，不会重置也不会减少。

实现代码

class Solution {
public:
    int longestAlternatingSubarray(vector<int>& nums, int threshold) {
        int n = nums.size(), res = 0;
        int i = 0;

        while (i < n) {
            if (nums[i] > threshold || nums[i] % 2) {
                ++i;
                continue;
            }
            int start = i;  // 子数组的开始
            ++i;            // 子数组开始位置已经满足，从下一个位置开始判断
            while (i < n && nums[i] <= threshold && nums[i] % 2 != nums[i-1] % 2) {
                ++i;
            }
            // 从 start 到 i-1 是符合条件的子数组
            res = max(res, i - start);
        }
        return res;
    }
};

以上代码，建议记住，尤其是用 if 来找符合子数组起点，一定会有读者想用 while 来实现，读者可以尝试一下，会遇到很多错误的，如果你最后将 while 语句调试通过了，欢迎评论区沟通交流，你很厉害！

记住的代码可以作为一个模板使用，用来解决 “数组会被分割成若干组，且每一组的判断/处理逻辑是一样的” 这一类问题。

复杂度分析

时间复杂度： $O (n)$ 。

空间复杂度： $O (1)$ 。

其他语言

python3

class Solution:
    def longestAlternatingSubarray(self, nums: List[int], threshold: int) -> int:
        n = len(nums)
        res, i = 0, 0
        while i < n:
            if nums[i] > threshold or nums[i] % 2:
                i += 1
                continue
            
            start = i
            i += 1
            while i < n and nums[i] <= threshold and nums[i] % 2 != nums[i-1] % 2:
                i += 1
            res = max(res, i - start)
        return res