376. 摆动序列

发表于 分类于 ， ， 阅读次数： 本文字数： 285 阅读时长 ≈ 1 分钟

思路: 先差分, 然后把所有0和相邻同号的数字(之一)去掉, 剩下的元素数量+2既是最终答案

注意: 元素个数为0, 元素个数为1, 差分后有0出现

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution
{
  public:
    int wiggleMaxLength(vector<int> &nums)
    {
        int size = nums.size() - 1;

        if (size < 1) { return size + 1; }

        int start = -1;

        for (int i = 0; i < size; i++) {
            nums[i] -= nums[i + 1];
            // find first not zero
            if (start == -1 && nums[i] != 0) { start = i; }
        }

        if (start == -1) {
            // none
            return 1;
        }

        int count = 1, want = nums[start];
        for (int i = start + 1; i < size; i++) {
            if ((nums[i] > 0 && want < 0) ||
                (nums[i] < 0 && want > 0)) {  // different sign and no zero
                want = nums[i];
                count++;
            }
        }

        return count + 1;
    }
};

看过题解: 复杂了, 只要统计波峰和波谷的数量就行了

别人的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) return n;
        
        int count = 1;
        for (int i = 1, prev_diff = 0; i < n; i++) {
            int diff = nums[i] - nums[i - 1];
            if (diff < 0) {
                if (prev_diff >= 0)
                    count++;
                prev_diff = -1;
            }
            if (diff > 0) {
                if (prev_diff <= 0)
                    count++;
                prev_diff = 1;
            }
        }
        return count;
    }
}

作者：lincs
链接：https://leetcode-cn.com/problems/wiggle-subsequence/solution/java-on-solution-by-lincs-6l5r/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。