当 A 的子数组 A[i], A[i+1], ..., A[j] 满足下列条件时,我们称其为湍流子数组:
也就是说,如果比较符号在子数组中的每个相邻元素对之间翻转,则该子数组是湍流子数组。
返回 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^9
本题其实是要我们求最长一段呈 ↗ ↘ ↗ ↘
或者 ↘ ↗ ↘ ↗
形状的数组长度。
看一眼数据范围,有 40000,那么枚举起点和终点,然后对划分出来的子数组检查是否为「湍流子数组」的朴素解法就不能过了。
朴素解法的复杂度为
,直接放弃朴素解法。
复杂度往下优化,其实就
的 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]
:不考虑,不符合「湍流」的定义代码:
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;
}
}
我们发现对于 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;
}
}
2 * 2
的数组空间。复杂度为 既然只需要记录上一行状态,能否直接将行的维度消除呢?
答案是可以的,当我们要转移第 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;
}
}
这是我们「刷穿 LeetCode」系列文章的第 No.*
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加,为了方便我们统计进度,我们将按照系列起始时的总题数作为分母,完成的题目作为分子,进行进度计算。当前进度为 */1916
。
为了方便各位同学能够电脑上进行调试和提交代码,我在 Github 建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里,你可以看到「系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。」