0%

LeetCode 376. Wiggle Subsequence

Posted on Edited on In

题目

原题在此

解析

满足一上一下的最长子序列. 一开始想用贪心, 代码如下.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() == 1) return 1;
        int res = 2;
        bool flag = nums[1] < nums[0];
        for(int i = 1; i < nums.size(); ++i) {
            if(!(nums[i] < nums[i - 1] == flag)) {
                flag = !flag;
                res++;
            }
        }
        return res;
    }
};

此方法无法解决nums[i] == nums[i - 1]的情况, 所以分成上下分开统计, 最后返回最大值

  1. nums[i+1] > nums[i]
    1. 假设 down[i] 表示的最长摆动序列的最远末尾元素下标正好为 i，遇到新的上升元素后，up[i+1] = down[i] + 1 ，这是因为 up 一定从 down 中产生（初始除外），并且 down[i] 此时最大。
    2. 假设 down[i] 表示的最长摆动序列的最远末尾元素下标小于 i，设为 j，那么 nums[j:i] 一定是递增的，因为若完全递减，最远元素下标等于 i，若波动，那么 down[i] > down[j]。由于 nums[j:i] 递增，down[j:i] 一直等于 down[j] ，依然满足 up[i+1] = down[i] + 1 。
  2. nums[i+1] < nums[i]，类似第一种情况
  3. nums[i+1] == nums[i]，新的元素不能用于任何序列，保持不变.

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() == 1) return 1;
        int up = 1, down = 1;
        for(int i = 1; i < nums.size(); ++i) {
            if(nums[i] < nums[i - 1]) down = up + 1;
            if(nums[i] > nums[i - 1]) up = down + 1;
        }
        return max(up, down);
    }
};