LeetCode 978. 最长湍流子数组

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 阿里
标签
数组 动态规划 滑动窗口

题目描述

✅ 978. 最长湍流子数组

image-20260929105437752

image-20260929105437912

题意分析

找到最长的连续子数组，使相邻大小关系严格交替：上升后必须下降，下降后必须上升。不能跳过元素；相等会中断交替。单个元素没有比较关系，也视为长度 1 的合法子数组。

解法：末步方向动态规划

核心思路

[!blue]

能否把当前元素接到前面的湍流段，只取决于前一段最后一次比较的方向。用 up、down 分别记录以当前位置结尾、最后一步上升或下降的最长长度。长度 1 没有方向，作为两种状态共同的起点。

若 arr[i] > arr[i - 1]，最后一步上升，只能接在上一个位置的下降状态后，得到 up = 旧 down + 1；以当前位置结尾且长度至少为 2 的子数组不可能最后一步下降，所以 down 重置为 1。连续两次上升时，旧 down 正好为 1，自然只保留当前相邻两项组成的长度 2。

若当前值更小，则对称地得到 down = 旧 up + 1，并将 up 重置为 1。若两值相等，任何包含这条相邻边的子数组都不合法，两个状态只能从当前单个元素重新开始，均设为 1。

对同一结尾和同一方向，较长的状态一定更有利，因为它与较短状态的后续扩展条件相同。因此每个方向只保留最长长度即可。每轮还要更新全局 answer，避免之后的重置覆盖已经在前面结束的最长段。

解题步骤

  1. 题目保证数组非空，令 up = down = answer = 1。
  2. 从第二项开始比较相邻元素。上升时先计算 up = down + 1，再令 down = 1。
  3. 下降时先计算 down = up + 1，再令 up = 1；相等时两者都重置为 1。
  4. 用当前 up、down 更新全局最大长度。
  5. 扫描结束返回 answer。单元素数组不进入循环，结果就是 1。

代码实现

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        // up/down：以当前位置结尾、最后一步为升/降的最长湍流长度。
        int up = 1;
        int down = 1;
        int answer = 1;

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[i - 1]) {
                // 本步上升，只能接在「上一步下降」的段后面。
                up = down + 1;
                down = 1;
            } else if (arr[i] < arr[i - 1]) {
                down = up + 1;
                up = 1;
            } else {
                // 相等切断交替，两个状态都从单元素重新开始。
                up = 1;
                down = 1;
            }

            answer = Math.max(answer, Math.max(up, down));
        }

        return answer;
    }
}

func maxTurbulenceSize(arr []int) int {
    // up/down：以当前位置结尾、最后一步为升/降的最长湍流长度。
    up, down := 1, 1
    answer := 1
    for i := 1; i < len(arr); i++ {
        if arr[i] > arr[i-1] {
            // 本步上升，只能接在「上一步下降」的段后面。
            up = down + 1
            down = 1
        } else if arr[i] < arr[i-1] {
            down = up + 1
            up = 1
        } else {
            // 相等切断交替，两个状态都从单元素重新开始。
            up, down = 1, 1
        }
        answer = max(answer, max(up, down))
    }
    return answer
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

  • 时间复杂度：$O(n)$，每对相邻元素只比较一次，每次更新常数个状态。
  • 空间复杂度：$O(1)$，只保留两个结尾状态和一个全局答案。

关键点总结

[!green]

  • 状态按结尾与最后方向区分，转移必须从相反方向接上。
  • 长度 1 是无方向的共同起点，让新的相邻不等元素可以组成长度 2。
  • 结尾状态可能缩短或重置，全局答案需要单独保存。

易错点总结

[!yellow]

  • 上升继续累加旧 up，会把连续同向的比较误当成交替。
  • 必须先读取旧的相反方向状态，再重置它，否则会丢掉可延长的长度。
  • 相等时不重置，会让子数组跨过不合法的相邻关系。
  • 重置为 0 会漏算当前元素，使下一次有效比较得到的长度少一。
  • 只返回最后位置的状态，会漏掉此前已经结束的更长湍流段。

相似题目

题目 难度 关联与区别
376. 摆动序列 中等 原题允许跳过元素形成摆动子序列，本题必须连续，比较方向不交替时要重置当前段。
674. 最长连续递增序列 简单 同样线性维护连续趋势长度，原题只接受上升，本题要求升降交替。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/82630774
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！