【Py/Java/C++三种语言详解】LeetCode每日一题240123【模拟】LeetCode2765、最长交替子数组

题目链接

LeetCode2765、最长交替子数组

题目描述

给你一个下标从 0 开始的整数数组 nums 。如果 nums 中长度为 m 的子数组 s 满足以下条件，我们称它是一个 交替子数组 ：

• m 大于 1 。
• s(1) = s(0) + 1 。
• 下标从 0 开始的子数组 s 与数组 [s(0), s(1), s(0), s(1),...,s((m-1) % 2)] 一样。也就是说，s(1) - s(0) = 1 ，s(2) - s(1) = -1 ，s(3) - s(2) = 1 ，s(4) - s(3) = -1 ，以此类推，直到 s[m - 1] - s[m - 2] = (-1)(m) 。

请你返回 nums 中所有 交替 子数组中，最长的长度，如果不存在交替子数组，请你返回 -1 。

子数组是一个数组中一段连续 非空 的元素序列。

示例 1：

输入：nums = [2,3,4,3,4]
输出：4
解释：交替子数组有 [3,4] ，[3,4,3] 和 [3,4,3,4] 。最长的子数组为 [3,4,3,4] ，长度为4 。

示例 2：

输入：nums = [4,5,6]
输出：2
解释：[4,5] 和 [5,6] 是仅有的两个交替子数组。它们长度都为 2 。

提示：

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 10^4

解题思路

可以设置一个增量d = ±1来表示当前交替子数组是应该递增1还是递减1。初始化为d = 1，表示交替子数组最初应该呈现上升趋势。同时初始化答案变量ans = -1和表示当前连续交替子数组的长度的变量cur_len = 1

从下标i = 1开始考虑所有近邻位置i和i-1，在一个while循环中进行。当

• nums[i] == nums[i-1] + d时，说明nums[i]可以延长在nums[i-1]后面，需要
  • 修改增量d要为其原来的相反数，即1变成-1，-1变成1，d = -d
  • 当连续交替子数组长度+1，cur_len += 1
  • 更新答案，ans = max(ans, cur_len)
  • 下标i前进，i += 1
• nums[i] != nums[i-1] + d时说明交替在此中断，重置cur_len = 1，同时考虑d是1还是-1。若
  • 若此时d为1，说明nums[i] != nums[i-1] + 1，即nums[i-1]不可能作为一个新的交替子数组的起始位置，下标i前进，i += 1
  • 若此时d为-1，只能说明nums[i] != nums[i-1] - 1，但有可能出现nums[i] == nums[i-1] + 1，即nums[i-1]可能成为一个新的交替子数组的起始位置，重置d为1，i暂时先保持不变

代码

Python

class Solution:
    def alternatingSubarray(self, nums: List[int]) -> int:
        # 增量变量，取值为1或-1，初始化为1
        d = 1
        # 答案变量
        ans = -1
        # 当前连续交替子数组的长度cur_len
        cur_len = 1
        # 设置下标从i开始
        i = 1
        while i < len(nums):
            # 如果当前元素nums[i]等于上一个元素nums[i-1]加上增量d
            # 则说明nums[i]可以延长在nums[i-1]后面
            if nums[i] == nums[i-1] + d:
                # 增量d要取其原来的相反数，即1变成-1，-1变成1
                d = -d
                # 当连续交替子数组长度+1
                cur_len += 1
                # 更新答案
                ans = max(ans, cur_len)
                i += 1
            # 否则，说明交替在此中断，重置cur_len
            else:
                cur_len = 1
                # 若此时d为1，说明nums[i] != nums[i-1] + 1
                # nums[i-1]不可能作为一个新的交替子数组的起始位置，i增加1
                if d == 1:
                    i += 1
                # 若此时d为-1，说明nums[i] != nums[i-1] + 1
                # 但有可能出现nums[i] == nums[i-1] - 1
                # 即nums[i-1]可能成为一个新的交替子数组的起始位置，重置d为1
                else:
                    d = 1

        # 最后返回ans即为答案
        return ans

Java

class Solution {
    public int alternatingSubarray(int[] nums) {
        int d = 1;
        int ans = -1;
        int curLen = 1;
        int i = 1;

        while (i < nums.length) {
            if (nums[i] == nums[i - 1] + d) {
                d = -d;
                curLen++;
                ans = Math.max(ans, curLen);
                i++;
            } else {
                curLen = 1;

                if (d == 1) {
                    i++;
                } else {
                    d = 1;
                }
            }
        }

        return ans;
    }
}

C++

class Solution {
public:
    int alternatingSubarray(std::vector<int>& nums) {
        int d = 1;
        int ans = -1;
        int curLen = 1;
        int i = 1;

        while (i < nums.size()) {
            if (nums[i] == nums[i - 1] + d) {
                d = -d;
                curLen++;
                ans = std::max(ans, curLen);
                i++;
            } else {
                curLen = 1;

                if (d == 1) {
                    i++;
                } else {
                    d = 1;
                }
            }
        }

        return ans;
    }
};

时空复杂度

时间复杂度：O(N)。仅需一次遍历数组

空间复杂度：O(1)。仅需若干变量

---

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多