LeetCode 376 - Wiggle Subsequence

作者 QIFAN 日期 2017-01-03
LeetCode 376 - Wiggle Subsequence

原题链接:376. Wiggle Subsequence


题干

wiggle sequence 就是一串数字中相邻数字的差严格遵循“正-负-正-负”的规律。少于两个元素的排列都是 wiggle sequence

给定一个数字数组,找出最长 wiggle sequence 子集长度。子集是删除一个或多个元素(当然也可以不删)后的原始数组。

举例
输入:[1,7,4,9,2,5]
输出: 6
解释:整个数组就是

输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 有很多长度为 7 的 wiggle sequence 子集。其中一个是 [1,17,10,13,10,16,8]

思路

  1. 简单粗暴。
    最直白的方式是找出所有子集,判断其是否为 wiggle ,求最大长度。
    这个时间复杂度为 $O(2^n)$
    下面来分析一下这里面有哪些不必计算或重复计算的部分。

  2. 优化过程
    如果某一段 (i, j) 为递增或者递减,那其实可以直接把中间的元素忽略。也不需要计算其子集。也可以看成将 i 和 j 当成相邻的 Wiggle 元素。这样子只需遍历一遍数组就可以完成。时间复杂度为 $O(n)$

  3. 最后方案
    写代码的时候有一些坑,需要注意。如果 (i, j) 之间为平稳的时候应该怎么办?我这里在计算差值时,将其算为前面累积的差。

    • (i, j) 在中间和开头,普通计算
    • (i, j) 在开头。那在碰到下一个 Wiggle 前,差一直为 0 。所以若差为 0 ,说明它是一段开头的平稳,需要在遇到 wiggle 时将长度增加。

代码:

public int wiggleMaxLength(int[] nums) {
if (nums.length < 2) {
return nums.length;
}
int maxLength = 1;
int lastDiff = nums[1] - nums[0];
if (lastDiff != 0) {
maxLength++;
}
int currDiff;
for (int i = 2; i < nums.length; i++) {
currDiff = nums[i] - nums[i - 1];
if (currDiff != 0) {
if (lastDiff == 0 || currDiff * lastDiff < 0) {
maxLength++;
lastDiff = currDiff;
} else {
lastDiff += currDiff;
}
}
}
return maxLength;
}