【Leetcode】376. Wiggle Subsequence

忘是亡心i 2022-04-16 04:18 144阅读 0赞

1.  Wiggle Subsequence

A sequence of numbers is called a **wiggle sequence** if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, `[1,7,4,9,2,5]` is a wiggle sequence because the differences `(6,-3,5,-7,3)` are alternately positive and negative. In contrast, `[1,4,7,2,5]` and `[1,7,4,5,5]` are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

**Example 1:**

Input: [1,7,4,9,2,5]
    Output: 6
    Explanation: The entire sequence is a wiggle sequence.

**Example 2:**

Input: [1,17,5,10,13,15,10,5,16,8]
    Output: 7
    Explanation: There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

**Example 3:**

Input: [1,2,3,4,5,6,7,8,9]
    Output: 2

**Follow up:**

Can you do it in O(*n*) time?

### 题解 ###

如果将数组看做是一副折线图就是求图中线条，出现的折点个数。我们可以使用两种方法来求解此问题：

1.  动态规划：
    
    如何动态规划呢，首先我们得考虑如何建立DP状态转移方程，在这个题目中，我们不难想到，数组从前往后总会出现两种状态，要要么上升，要么下降，我们的状态转移方程就是如果是当前位置是下降，那么就用上升的最大值+1，如果当前位置处于下降，则需要使用下降的最大值来+1，最后我们比较到底是上升多，还是下降大即可，因为最后一次，我们也不知道是上升还是下降，所以我们需要比较。如果即不上升也不下降代表此时是平行线，无需处理。
    
    定义变量 up =1 , down =1 ,初始化时即可以认为是上升也可以认为是下降。
    
    如果`num[i] > num[i-1]` 则 `up=down+1`，
    
    如果`num[i] < num[i-1]` 则 `down=up+1`，
2.  贪心算法：
    
    从头开始遍历，使用贪心规则，保证满足折点要求的都几率，我们定义一个前缀遍历`prev`，用来保存上一次两个数相减的结果，如果这一次与上一次的刚好相反，则纳入结果中。然后更新前缀`prev`为这一次的相减结果。需要注意的点是，对于初始化的时候，如果相减结果为`0`则我们需要跳过不处理。

### 代码 ###

DP解法一:

public static int wiggleMaxLength(int[] nums) { 
            if (nums.length < 2) { 
                return nums.length;
            }
    
            int up[] = new int[nums.length];
            int down[] = new int[nums.length];
    
            for (int i = 1; i < nums.length; i++) { 
                for (int j = 0; j < i; j++) { 
                    if (nums[i] > nums[j]) { 
                        up[i] = Math.max(up[i], down[j] + 1);
                    } else if (nums[i] < nums[j]) { 
                        down[i] = Math.max(up[j] + 1, down[i]);
                    }
                }
            }
            return 1 + Math.max(down[nums.length - 1], up[nums.length - 1]);
        }

DP解法二：

public static int wiggleMaxLength(int[] nums) { 
            if (nums.length < 2) { 
                return nums.length;
            }
    
            int up = 1, down = 1;
    
            for (int i = 1; i < nums.length; i++) { 
                if (nums[i] > nums[i - 1]) { 
                    up = down + 1;
                } else if (nums[i] < nums[i - 1]) { 
                    down = up + 1;
                }
            }
            return Math.max(up, down);
        }

贪心：

public static int wiggleMaxLength(int[] nums) { 
            if (nums.length < 2) { 
                return nums.length;
            }
    
            int prev = nums[1] - nums[0];
            int cnt = prev == 0 ? 1 : 2;
            for (int i = 1; i < nums.length; i++) { 
                int diff = nums[i] - nums[i - 1];
                if ((diff > 0 && prev <= 0) || (diff < 0 && prev >= 0)) { 
                    cnt++;
                    prev = diff;
                }
            }
            return cnt;
    
        }