LC.P2760[最长奇偶子数组]

方法一：枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int longestAlternatingSubarray(int[] nums, int threshold) {
        int n = nums.length, ans = 0;
        for (int l = 0; l < n; ++l) {
            if (nums[l] % 2 == 0 && nums[l] <= threshold) {
                int r = l + 1;
                while (r < n && nums[r] % 2 != nums[r - 1] % 2 && nums[r] <= threshold) {
                    ++r;
                }
                ans = Math.max(ans, r - l);
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(1)$

方法二：优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int longestAlternatingSubarray(int[] nums, int threshold) {
        int n = nums.length, ans = 0;
        for (int l = 0; l < n; ) {
            if (nums[l] % 2 == 0 && nums[l] <= threshold) {
                int r = l + 1;
                while (r < n && nums[r] % 2 != nums[r - 1] % 2 && nums[r] <= threshold) {
                    ++r;
                }
                ans = Math.max(ans, r - l);
                l = r;
            } else {
                ++l;
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$