题目描述
这是 LeetCode 上的 978. 最长湍流子数组 。
Tag : 「序列 DP」
当 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：
输入：[4,8,12,16] 输出：2 复制代码
示例 3：
输入：[100] 输出：1 复制代码
提示：
- 1 <= A.length <= 40000
- 0 <= A[i] <= 10^9109
基本分析思路
本题其实是要我们求最长一段呈 ↗ ↘ ↗ ↘ 或者 ↘ ↗ ↘ ↗ 形状的数组长度。
看一眼数据范围，有 40000，那么枚举起点和终点，然后对划分出来的子数组检查是否为「湍流子数组」的朴素解法就不能过了。
朴素解法的复杂度为 O(n^3)O(n3) ，直接放弃朴素解法。
复杂度往下优化，其实就 O(n)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] + 1arr[i - 1] > arr[i]：改点是由下降而来，能够「接着」的条件是i - 1是由上升而来。则有：f[i][1] = f[i - 1][0] + 1arr[i - 1] = arr[i]：不考虑，不符合「湍流」的定义
代码：
class Solution { public int maxTurbulenceSize(int[] arr) { int n = arr.length; int ans = 1; int[][] f = new int[n][2]; for (int i = 0; i < 2; i++) f[0][i] = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < 2; j++) f[i][j] = 1; if (arr[i - 1] < arr[i]) f[i][0] = f[i - 1][1] + 1; if (arr[i - 1] > arr[i]) f[i][1] = f[i - 1][0] + 1; for (int j = 0; j < 2; j++) ans = Math.max(ans, f[i][j]); } return ans; } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：O(n)O(n)
动态规划（空间优化：奇偶滚动）
我们发现对于 f[i][j] 状态的更新只依赖于 f[i - 1][j] 的状态。
因此我们可以使用「奇偶滚动」方式来将第一维从 n 优化到 2 。
修改的方式也十分机械，只需要改为「奇偶滚动」的维度直接修改成 2 ，然后该维度的所有访问方式增加 %2 即可：
class Solution { public int maxTurbulenceSize(int[] arr) { int n = arr.length; int ans = 1; int[][] f = new int[2][2]; for (int i = 0; i < 2; i++) f[0][i] = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < 2; j++) f[i % 2][j] = 1; if (arr[i - 1] < arr[i]) f[i % 2][0] = f[(i - 1) % 2][1] + 1; if (arr[i - 1] > arr[i]) f[i % 2][1] = f[(i - 1) % 2][0] + 1; for (int j = 0; j < 2; j++) ans = Math.max(ans, f[i % 2][j]); } return ans; } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：使用固定
2 * 2的数组空间。复杂度为 O(1)O(1)
动态规划（空间优化：维度消除）
既然只需要记录上一行状态，能否直接将行的维度消除呢？
答案是可以的，当我们要转移第 i 行的时候，f 数组装的就已经是 i - 1 行的结果。
这也是著名「背包问题」的一维通用优手段。
但相比于「奇偶滚动」的空间优化，这种优化手段只是常数级别的优化（空间复杂度与「奇偶滚动」相同），而且优化通常涉及代码改动。
class Solution { public int maxTurbulenceSize(int[] arr) { int n = arr.length; int ans = 1; int[] f = new int[2]; for (int i = 0; i < 2; i++) f[i] = 1; for (int i = 1; i < n; i++) { int dp0 = f[0], dp1 = f[1]; if (arr[i - 1] < arr[i]) { f[0] = dp1 + 1; } else { f[0] = 1; } if (arr[i - 1] > arr[i]) { f[1] = dp0 + 1; } else { f[1] = 1; } for (int j = 0; j < 2; j++) ans = Math.max(ans, f[j]); } return ans; } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：O(1)O(1)
其他
如果你对「猜 DP 的状态定义」还没感觉，这里有道类似的题目可以瞧一眼：45. 跳跃游戏 II
最后
这是我们「刷穿 LeetCode」系列文章的第 No.978 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
