最长湍流子数组
难度:
标签:
题目描述
代码结果
运行时间: 66 ms, 内存: 18.8 MB
/*
* 思路:
* 使用流处理方法,首先创建一个差值数组diff,记录相邻元素的差值,然后根据差值正负交替的规则来计算最大湍流子数组的长度。
*/
import java.util.stream.IntStream;
public class Solution {
public int maxTurbulenceSize(int[] arr) {
if (arr.length == 1) return 1;
int maxLen = 1;
int increasing = 1, decreasing = 1;
int[] diff = IntStream.range(1, arr.length)
.map(i -> Integer.compare(arr[i], arr[i - 1]))
.toArray();
for (int i = 0; i < diff.length; i++) {
if (diff[i] == 1) {
increasing = decreasing + 1;
decreasing = 1;
} else if (diff[i] == -1) {
decreasing = increasing + 1;
increasing = 1;
} else {
increasing = 1;
decreasing = 1;
}
maxLen = Math.max(maxLen, Math.max(increasing, decreasing));
}
return maxLen;
}
}
解释
方法:
该题解使用动态规划方法求解最长湍流子数组的长度。定义dp[i]表示以arr[i]结尾的最长湍流子数组的长度。使用tail变量记录上一个元素的值,sign变量记录当前湍流子数组的比较符号,即在湍流子数组中,当前比较应该是大于还是小于。初始时,dp数组全部初始化为1(每个元素自身至少是长度为1的湍流子数组),tail初始化为arr[0],sign初始化为0(表示还未确定比较方向)。遍历数组时,根据当前元素与tail的比较结果以及当前的sign状态,更新dp数组。如果当前元素与tail相等,湍流结束,dp[i]重置为1;如果符合当前的湍流模式(sign状态),则dp[i]等于dp[i-1]+1并更新sign;如果不符合当前模式,根据具体情况重置sign和dp[i]的值。最后返回dp数组中的最大值,即为最长的湍流子数组长度。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在算法中,为什么在遇到当前元素与tail相等时,需要将dp[i]重置为1?这对于识别湍流子数组的边界有何作用?
▷🦆
题解中提到当当前元素不符合湍流模式时,dp[i]会被设置为2,这里的逻辑是基于什么考虑?
▷🦆
题解中的sign变量在确定比较方向时有三种状态(0,1,-1),每种状态具体代表什么?
▷🦆
为什么题解中在遍历数组时需要从索引1开始,而不是从头开始遍历?
▷相关问题
最大子数组和
给你一个整数数组 nums
,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4] 输出:6 解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:
输入:nums = [1] 输出:1
示例 3:
输入:nums = [5,4,-1,7,8] 输出:23
提示:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
进阶:如果你已经实现复杂度为 O(n)
的解法,尝试使用更为精妙的 分治法 求解。