摆动序列
难度:
标签:
题目描述
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
-
例如，
[1, 7, 4, 9, 2, 5]是一个 摆动序列 ，因为差值(6, -3, 5, -7, 3)是正负交替出现的。 - 相反，
[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例 1：
输入：nums = [1,7,4,9,2,5] 输出：6 解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
示例 2：
输入：nums = [1,17,5,10,13,15,10,5,16,8] 输出：7 解释：这个序列包含几个长度为 7 摆动序列。 其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
示例 3：
输入：nums = [1,2,3,4,5,6,7,8,9] 输出：2
提示：
1 <= nums.length <= 10000 <= nums[i] <= 1000
进阶：你能否用 O(n) 时间复杂度完成此题?
代码结果
运行时间: 17 ms, 内存: 16.1 MB
/*
* 使用Java Stream实现的思路：
* 1. 如果nums的长度小于2，直接返回nums的长度。
* 2. 创建一个AtomicInteger来记录当前up的值，另一个记录down的值。
* 3. 使用IntStream.range从1遍历到nums.length - 1。
* 4. 在forEach中比较相邻元素的差值，更新up和down。
* 5. 最后返回up和down中的最大值。
*/
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.IntStream;
public class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2) return nums.length;
AtomicInteger up = new AtomicInteger(1);
AtomicInteger down = new AtomicInteger(1);
IntStream.range(1, nums.length).forEach(i -> {
if (nums[i] > nums[i - 1]) {
up.set(down.get() + 1);
} else if (nums[i] < nums[i - 1]) {
down.set(up.get() + 1);
}
});
return Math.max(up.get(), down.get());
}
}解释
方法:
这个题解的思路是遍历数组，用一个变量 flag 来记录前一个差值的正负。如果当前差值和前一个差值符号相反，则摆动序列长度加1，并更新 last 为当前元素。如果当前差值和前一个差值符号相同，则只更新 last 为当前元素，不增加摆动序列长度。flag 初始为0，遇到第一个非0差值时，根据正负设置 flag 为1或-1。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
题解中提到使用flag来记录前一个差值的正负，初始值为0。请问在什么情况下flag会保持为0，这是否影响算法的正确性和完整性？
▷🦆
在题解的算法中，当连续出现多个相同的数字时，如何处理这些数字，它们是否会被计入摆动序列的长度？
▷🦆
题解中提到当遇到第一个非0差值时，会根据差值的正负来设置flag。但在实际操作中，如何确保处理的是第一个非0差值，而不是之后的某个非0差值？
▷🦆
在更新flag和last的逻辑中，题解似乎没有考虑到数组中所有元素都相同的情况。在这种特殊情况下，算法的输出是否正确？
▷