leetcode-wiggle-subsequence

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/wiggle-subsequence/

　　给你一个数组，让你找出一个满足这样性质的最长子序列，子序列中元素总是相邻元素高地起伏，画成曲线呈现严格锯齿状。

题目分析

　　本题将数组化成直方图以后，实际上是找每个局部的极值点，根据数学知识，离散的局部极值点是左右差值异号的，比如a，b，c三点，b是局部极值点，那么(a - b) * (b - c) < 0，但一些特殊情况要考虑，比如最开始是平的，突然上升或者下降

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int wiggleMaxLength(vector<int>& nums) {
    int s = nums.size();
    if(s <= 1) {
        return s;
    }
    int ans = 1;
    int diff = nums[0] - nums[1];
    if(diff != 0) {
        ans++;
    }
    for(int i = 2; i < s; i++) {
        if(nums[i - 1] != nums[i]) {
            if(diff * (nums[i - 1] - nums[i]) <= 0) {
               ans++;
               diff = nums[i - 1] - nums[i];
            }
        }
    }
    return ans;
}

　　注意for循环里：当nums[i - 1]!=nums[i]出现时才有必要更新ans，diff，不然是平的情况不需要更新，或者说还没有到极值点。满足条件后，再判断diff * (nums[i - 1] - nums[i]) < 0那么肯定有多了个极值点，因此ans++，同时更新diff。注意要加上等于0，如果不加，考虑一个数组3 3 3 2 5，那么diff永远是0。

　　算法复杂度是：O(n)