leetcode
leetcode 901 ~ 950
最长湍流子数组

最长湍流子数组

难度:

标签:

题目描述

代码结果

运行时间: 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?这对于识别湍流子数组的边界有何作用?
在湍流子数组中,要求每个元素与前一个元素不相等,并且与前一个元素的大小关系要连续交替。当当前元素与tail(即前一个元素)相等时,这种大小关系被打破,因此无法形成湍流子数组。将dp[i]重置为1是因为任何单个元素可以被视为长度为1的湍流子数组。这种处理有助于在数组中明确标识湍流子数组的起始点,即每次遇到相等的元素,湍流子数组就在此处结束,新的可能的湍流子数组从下一个不同的元素开始。
🦆
题解中提到当当前元素不符合湍流模式时,dp[i]会被设置为2,这里的逻辑是基于什么考虑?
如果当前元素不符合预期的湍流模式(即大于或小于之间的交替关系被破坏),但同时与前一个元素不相等,意味着这个元素可以与前一个元素组成一个新的长度为2的湍流子数组。此时,虽然不能延续之前的湍流子数组,但可以开始一个新的湍流子数组,因此dp[i]被设置为2。这反映了题解中尝试从每个可能的点重新开始计算湍流子数组的长度的策略。
🦆
题解中的sign变量在确定比较方向时有三种状态(0,1,-1),每种状态具体代表什么?
在题解中,sign变量用于表示当前湍流子数组中元素的比较方向。其中,0表示比较方向尚未确定,通常是在子数组开始的位置或者当前元素与前一个元素相等时使用。1表示当前元素应该大于前一个元素,即预期下一个元素应该小于当前元素,形成一个'大于'的比较。-1表示当前元素应该小于前一个元素,即预期下一个元素应该大于当前元素,形成一个'小于'的比较。这种方法有助于追踪和维持湍流子数组的交替大小关系。
🦆
为什么题解中在遍历数组时需要从索引1开始,而不是从头开始遍历?
题解中从索引1开始遍历数组是因为需要将数组中的每个元素与其前一个元素进行比较。如果从索引0开始,则没有前一个元素可以用于比较,无法决定该元素与前一个元素的大小关系,因此无法判断是否符合湍流条件。从索引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) 的解法,尝试使用更为精妙的 分治法 求解。