最长湍流子数组 图解题解

最长湍流子数组，这道题到底在找什么

给一个整数数组 arr，找最长的「湍流」子数组，返回长度。湍流就是相邻两数一升一降交替：大、小、大、小，或小、大、小、大，一旦相等或连续同向，交替就断。子数组要连续、不能跳挑。比如 arr=[4,8,12,16] 一路上升，最多取相邻两个得 2；arr=[100] 单数一段得 1。

为什么不能把每一段子数组都截出来验一遍

连续子数组有 O(n²) 段（大 O 记号，描述规模变大时操作数怎么涨），每段还要 O(n) 验符号是否交替，合起来 O(n³)，稍长就跑不动。而且大量重叠：短段 4、2、10、7 验过，长段接上 8 又从头查一遍。既然长段就是短段接一个数，就不必每段重验，只盯「以当前数结尾、还在生长的湍流段有多长」往后接即可。

一个升态一个降态，为什么非得分开记两个长度

这里用动态规划（以当前数结尾的湍流段长算一次存 up/down，下一步直接接）。只记一个「当前最长湍流段」不够：下一步能不能接，取决于当前段结尾那步是升还是降。

所以拆成两个状态（记扫到当前为止两种局面各自的最长长度）：up 是以当前数结尾、最后一步上升的最长段长，down 是最后一步下降的。两个都从 1 起，单数就是长度 1 的段。

升接旧 down、降接旧 up，两个状态怎么互相接力

扫到新数先和前一个比。这一步上升（前一个小于当前），要交替，前一段结尾得是下降，新 up 接旧 down：up = 旧 down + 1，同向的 down 归 1。这步下降反过来，新 down = 旧 up + 1，up 归 1。两数相等既不升也不降，湍流断掉，up、down 一起归 1、重数。每处理完一个数，用 up、down 刷新全局最长答案。

落到代码上，升态记成 f、降态记成 g，都从 1 起；每步先用 ff、gg 暂存新值再一起赋回，免得先改的盖掉要读的旧值。

把题面例子的 up、down 亲手走一遍

拿 arr=[9,4,2,10,7,8,8,1,9] 走一遍：起手 up=down=ans=1。扫 4 比 9 小是降，down = 旧 up + 1 = 2，ans=2；扫 2 仍降，down = 2；扫 10 转升，up = 旧 down + 1 = 3，ans=3；扫 7 又降，down = 旧 up + 1 = 4，ans=4；扫 8 转升，up = 旧 down + 1 = 5，ans=5；再扫 8 相等，硬断，up、down 全归 1，ans 留 5；扫 1 降，down = 2；扫 9 升，up = 旧 down + 1 = 3。全程最大 5，就是 4、2、10、7、8，符号大、小、大、小交替。

相等那步忘把 up、down 一起归 1，湍流为什么会假装没断

扫一遍、每数只比一次，时间 O(n)；只留 up、down、ans 三个量轮换，空间 O(1)，不用开二维表。

相等是最容易漏的硬断：符号一断，up、down 必须同时归 1、只清当前段，忘了归 1 会让后面错把断点前的长度接着算。ans 别跟着清，它记全程见过的最长，两个 8 打断后仍停在 5，每断就重置会把攒下的最长丢光。边界：单数返回 1，单调或全相等最多 2 或 1。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        ans = f = g = 1
        for a, b in pairwise(arr):
            ff = g + 1 if a < b else 1
            gg = f + 1 if a > b else 1
            f, g = ff, gg
            ans = max(ans, f, g)
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int ans = 1, f = 1, g = 1;
        for (int i = 1; i < arr.size(); ++i) {
            int ff = arr[i - 1] < arr[i] ? g + 1 : 1;
            int gg = arr[i - 1] > arr[i] ? f + 1 : 1;
            f = ff;
            g = gg;
            ans = max({ans, f, g});
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int ans = 1, f = 1, g = 1;
        for (int i = 1; i < arr.length; ++i) {
            int ff = arr[i - 1] < arr[i] ? g + 1 : 1;
            int gg = arr[i - 1] > arr[i] ? f + 1 : 1;
            f = ff;
            g = gg;
            ans = Math.max(ans, Math.max(f, g));
        }
        return ans;
    }
}