LC 978. 最长湍流子数组

题目描述

这是 LeetCode 上的 978. 最长湍流子数组 ，难度为中等。

当 A 的子数组 $A[i], A[i+1], …, A[j]$ 满足下列条件时，我们称其为湍流子数组：

若 $i <= k < j$，当 $k$ 为奇数时，$A[k] > A[k+1]$，且当 $k$ 为偶数时，$A[k] < A[k+1]$；
若 $i <= k < j$，当 $k$ 为偶数时，$A[k] > A[k+1]$ ，且当 $k$ 为奇数时，$A[k] < A[k+1]$。

也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。

返回 A 的最大湍流子数组的长度。

示例 1：

输入：[9,4,2,10,7,8,8,1,9]

输出：5

解释：(A[1] > A[2] < A[3] > A[4] < A[5])

示例 2：

1
2
3

输入：[4,8,12,16]

输出：2

示例 3：

1
2
3

输入：[100]

输出：1

提示：

$1 <= A.length <= 40000$
$0 <= A[i] <= 10^9$

基本思路

本题其实是要我们求最长一段呈 ↗ ↘ ↗ ↘ 或者 ↘ ↗ ↘ ↗ 形状的数组长度。

看一眼数据范围，有 $40000$，那么枚举起点和终点，然后对划分出来的子数组检查是否为「湍流子数组」的朴素解法就不能过了。

朴素解法的复杂度为 $O(n^3)$ ，直接放弃朴素解法。

复杂度往下优化，其实就 $O(n)$ 的 DP 解法了。

动态规划

至于 DP 如何分析，通过我们会先考虑一维 DP 能否求解，不行再考虑二维 DP。

对于本题，由于每个位置而言，能否「接着」上一个位置形成「湍流」，取决于上一位置是由什么形状而来。

举个例子，对于样例 [3,4,2]，从 4 -> 2 已经确定是 ↘ 状态，那么对于 2 这个位置能否「接着」4 形成「湍流」，要求 4 必须是由 ↗ 而来。

因此我们还需要记录某一位是如何来的（↗ 还是 ↘），需要使二维 DP 来求解 ~

我们定义 $f[i][j]$ 代表以位置 $i$ 为结尾，而结尾状态为 $j$ 的最长湍流子数组长度（0：上升状态 / 1:下降状态）

PS. 这里的状态定义我是猜的，这其实是个技巧。通常我们做 DP 题，都是先猜一个定义，然后看看这个定义是否能分析出状态转移方程帮助我们「不重不漏」的枚举所有的方案。一般我是直接根据答案来猜定义，这里是求最长子数组长度，所以我猜一个 f(i,j) 代表最长湍流子数组长度

不失一般性考虑 $f[i][j]$ 该如何求解，我们知道位置 $i$ 是如何来是唯一确定的（取决于 $arr[i]$ 和 $arr[i - 1]$ 的大小关系），而只有三种可能性：

$arr[i - 1] < arr[i]$：该点是由上升而来，能够「接着」的条件是 $i - 1$ 是由下降而来。则有：$f[i][0] = f[i - 1][1] + 1$
$arr[i - 1] > arr[i]$：改点是由下降而来，能够「接着」的条件是 $i - 1$ 是由上升而来。则有：$f[i][1] = f[i - 1][0] + 1$
$arr[i - 1] = arr[i]$：不考虑，不符合「湍流」的定义

Java 代码：

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length, ans = 1;
        int[][] f = new int[n][2];
        f[0][0] = f[0][1] = 1;
        for (int i = 1; i < n; i++) {
            f[i][0] = f[i][1] = 1;
            if (arr[i] > arr[i - 1]) f[i][0] = f[i - 1][1] + 1;
            else if (arr[i] < arr[i - 1]) f[i][1] = f[i - 1][0] + 1;
            ans = Math.max(ans, Math.max(f[i][0], f[i][1]));
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size(), ans = 1;
        vector<vector<int>> f(n, vector<int>(2, 1));
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) f[i][0] = f[i - 1][1] + 1;    
            else if (arr[i] < arr[i - 1]) f[i][1] = f[i - 1][0] + 1;
            ans = max(ans, max(f[i][0], f[i][1]));
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        n, ans = len(arr), 1
        f = [[1, 1] for _ in range(n)]
        for i in range(1, n):
            if arr[i] > arr[i - 1]:
                f[i][0] = f[i - 1][1] + 1
            elif arr[i] < arr[i - 1]:
                f[i][1] = f[i - 1][0] + 1
            ans = max(ans, max(f[i][0], f[i][1]))
        return ans

TypeScript 代码：

function maxTurbulenceSize(arr: number[]): number {
    let n = arr.length, ans = 1;
    const f: number[][] = new Array(n).fill(0).map(() => [1, 1]);
    for (let i = 1; i < n; i++) {
        if (arr[i] > arr[i - 1]) f[i][0] = f[i - 1][1] + 1;
        else if (arr[i] < arr[i - 1]) f[i][1] = f[i - 1][0] + 1;
        ans = Math.max(ans, Math.max(f[i][0], f[i][1]));
    }
    return ans;
};

时间复杂度：$O(n)$
空间复杂度：$O(n)$

空间优化：奇偶滚动

我们发现对于 $f[i][j]$ 状态的更新只依赖于 $f[i - 1][j]$ 的状态。

因此我们可以使用「奇偶滚动」方式来将第一维从 $n$ 优化到 $2$。

修改的方式也十分机械，只需要改为「奇偶滚动」的维度直接修改成 $2$ ，然后该维度的所有访问方式增加 %2 或者 &1 即可：

Java 代码：

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length, ans = 1;
        int[][] f = new int[2][2];
        f[0][0] = f[0][1] = 1;
        for (int i = 1; i < n; i++) {
            f[i % 2][0] = f[i % 2][1] = 1;
            if (arr[i] > arr[i - 1]) f[i % 2][0] = f[(i - 1) % 2][1] + 1;
            else if (arr[i] < arr[i - 1]) f[i % 2][1] = f[(i - 1) % 2][0] + 1;
            ans = Math.max(ans, Math.max(f[i % 2][0], f[i % 2][1]));
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size(), ans = 1;
        vector<vector<int>> f(2, vector<int>(2, 1));
        for (int i = 1; i < n; i++) {
            f[i % 2][0] = f[i % 2][1] = 1;
            if (arr[i] > arr[i - 1]) f[i % 2][0] = f[(i - 1) % 2][1] + 1;
            else if (arr[i] < arr[i - 1]) f[i % 2][1] = f[(i - 1) % 2][0] + 1;
            ans = max(ans, max(f[i % 2][0], f[i % 2][1]));
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        n, ans = len(arr), 1
        f = [[1, 1] for _ in range(2)]
        for i in range(1, n):
            f[i % 2][0] = f[i % 2][1] = 1
            if arr[i] > arr[i - 1]:
                f[i % 2][0] = f[(i - 1) % 2][1] + 1
            elif arr[i] < arr[i - 1]:
                f[i % 2][1] = f[(i - 1) % 2][0] + 1
            ans = max(ans, max(f[i % 2][0], f[i % 2][1]))
        return ans

TypeScript 代码：

function maxTurbulenceSize(arr: number[]): number {
    let n = arr.length, ans = 1;
    const f: number[][] = [[1, 1], [1, 1]];
    for (let i = 1; i < n; i++) {
        f[i % 2][0] = f[i % 2][1] = 1;
        if (arr[i] > arr[i - 1]) f[i % 2][0] = f[(i - 1) % 2][1] + 1;
        else if (arr[i] < arr[i - 1]) f[i % 2][1] = f[(i - 1) % 2][0] + 1;
        ans = Math.max(ans, Math.max(f[i % 2][0], f[i % 2][1]));
    }
    return ans;
};

时间复杂度：$O(n)$
空间复杂度：使用固定 2 * 2 的数组空间。复杂度为 $O(1)$

空间优化：维度消除

既然只需要记录上一行状态，能否直接将行的维度消除呢？

答案是可以的，当我们要转移第 $i$ 行的时候，$f[i]$ 装的就已经是 $i - 1$ 行的结果。

这也是著名「背包问题」的一维通用优手段。

但相比于「奇偶滚动」的空间优化，这种优化手段只是常数级别的优化（空间复杂度与「奇偶滚动」相同），而且优化通常涉及代码改动。

Java 代码：

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length, ans = 1;
        int[] f = new int[2];
        f[0] = f[1] = 1;
        for (int i = 1; i < n; i++) {
            int a = f[0], b = f[1];
            f[0] = arr[i - 1] < arr[i] ? b + 1 : 1;
            f[1] = arr[i - 1] > arr[i] ? a + 1 : 1;
            ans = Math.max(ans, Math.max(f[0], f[1]));
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size(), ans = 1;
        vector<int> f(2, 1);
        for (int i = 1; i < n; ++i) {
            int a = f[0], b = f[1];
            f[0] = arr[i - 1] < arr[i] ? b + 1 : 1;
            f[1] = arr[i - 1] > arr[i] ? a + 1 : 1;
            ans = max(ans, max(f[0], f[1]));
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        n, ans = len(arr), 1
        f = [1, 1]
        for i in range(1, n):
            a, b = f[0], f[1]
            f[0] = b + 1 if arr[i - 1] < arr[i] else 1
            f[1] = a + 1 if arr[i - 1] > arr[i] else 1
            ans = max(ans, max(f[0], f[1]))
        return ans

TypeScript 代码：

function maxTurbulenceSize(arr: number[]): number {
    let n = arr.length, ans = 1;
    let f = [1, 1];
    for (let i = 1; i < n; i++) {
        let [a, b] = f;
        f[0] = arr[i - 1] < arr[i] ? b + 1 : 1;
        f[1] = arr[i - 1] > arr[i] ? a + 1 : 1;
        ans = Math.max(ans, Math.max(f[0], f[1]));
    }
    return ans;
};

时间复杂度：$O(n)$
空间复杂度：$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.978 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

序列 DP 线性 DP

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 992. K 个不同整数的子数组上一篇

LC 1749. 任意子数组和的绝对值的最大值下一篇