最长湍流子数组 图解题解

这道题到底在问什么

输入

arr=[9,4,2,10,7,8,8,1,9]

输出

5 （4 大 2 小 10 大 7 小 8，比较符交替）

输入

arr=[4,8,12,16]

输出

2 （一路上升不翻转，最多取相邻两个）

输入

arr=[100]

输出

1 （单个元素自成一段）

最优解：一步一步想明白

1. 3记住这套「升就 up 接旧 down、降就 down 接旧 up、相等全归 1，每步刷新答案」，下面每一帧都在套它。
2. 4开局:第 0 个元素 9 自己就是一段长度 1 的湍流段(绿色)。up 和 down 都初始化成 1，从第 1 个起才有「前一个」可比。
3. 5扫到第 1 个 4，和前一个 9 比。绿色是到上一个为止还在生长的湍流段(长度 1)，此刻 up=1、down=1。看着是下降，下一帧看 down 怎么接。
4. 64 比 9 小，这一步是下降。反过来，新的 down 接在「上一个结尾是上升」的段后面:down = 旧 up + 1 = 2;up 归 1。刷新答案 ans=2。
5. 7扫到第 2 个 2，和前一个 4 比。绿色是到上一个为止还在生长的湍流段(长度 2)，此刻 up=1、down=2。看着是下降，下一帧看 down 怎么接。
6. 82 比 4 小，这一步是下降。反过来，新的 down 接在「上一个结尾是上升」的段后面:down = 旧 up + 1 = 2;up 归 1。还没超过 ans=2，答案不动。
7. 9扫到第 3 个 10，和前一个 2 比。绿色是到上一个为止还在生长的湍流段(长度 2)，此刻 up=1、down=2。看着是上升，下一帧看 up 怎么接。
8. 1010 比 2 大，这一步是上升。湍流要交替，所以新的 up 接在「上一个结尾是下降」的段后面:up = 旧 down + 1 = 3;同向接不上的 down 归 1。这个 3 比旧答案大，刷新 ans=3。
9. 11扫到第 4 个 7，和前一个 10 比。绿色是到上一个为止还在生长的湍流段(长度 3)，此刻 up=3、down=1。看着是下降，下一帧看 down 怎么接。
10. 127 比 10 小，这一步是下降。反过来，新的 down 接在「上一个结尾是上升」的段后面:down = 旧 up + 1 = 4;up 归 1。刷新答案 ans=4。
11. 13扫到第 5 个 8，和前一个 7 比。绿色是到上一个为止还在生长的湍流段(长度 4)，此刻 up=1、down=4。看着是上升，下一帧看 up 怎么接。
12. 148 比 7 大，这一步是上升。湍流要交替，所以新的 up 接在「上一个结尾是下降」的段后面:up = 旧 down + 1 = 5;同向接不上的 down 归 1。这个 5 比旧答案大，刷新 ans=5。
13. 15扫到第 6 个 8，和前一个 8 比。绿色是到上一个为止还在生长的湍流段(长度 5)，此刻 up=5、down=1。两个数一样大，怕是要断，下一帧见分晓。
14. 168 和 8 一样大，既不算上升也不算下降，湍流彻底断在这里。up 和 down 同时归 1，从第 6 个重新数。注意 ans 仍保留着 5，断开只清空当前段，绝不抹掉历史最长。
15. 17扫到第 7 个 1，和前一个 8 比。绿色是到上一个为止还在生长的湍流段(长度 1)，此刻 up=1、down=1。看着是下降，下一帧看 down 怎么接。
16. 181 比 8 小，这一步是下降。反过来，新的 down 接在「上一个结尾是上升」的段后面:down = 旧 up + 1 = 2;up 归 1。还没超过 ans=5，答案不动。
17. 19全部扫完。一路上 up 和 down 此消彼长，最长的一段湍流是高亮的这 5 个:4、2、10、7、8，比较符大、小、大、小完整交替。后面 8、8 相等把湍流打断，所以没能更长。答案 5。
18. 20回放这段赢家，看比较符怎么一步步翻转。先单看第 1 个 4，长度 1。
19. 214 到 2 是下降，比较符是「大」，和前一对正式开头，交替成立，长度到 2。
20. 222 到 10 是上升，比较符是「小」，和前一对正好相反，交替成立，长度到 3。
21. 2310 到 7 是下降，比较符是「大」，和前一对正好相反，交替成立，长度到 4。
22. 247 到 8 是上升，比较符是「小」，和前一对正好相反，交替成立，长度到 5。比较符一路 大、小、大、小 交替，五个元素，答案就是 5。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问