LeetCode_ 376_ Wobble sequence

Topic link

• https://leetcode.cn/problems/wiggle-subsequence/

Title Description

If the difference between consecutive numbers strictly alternates between positive and negative numbers , Then the sequence of numbers is called Swing sequence . First difference （ If it exists ） It could be positive or negative . A sequence with only one element or two unequal elements is also regarded as a swing sequence .

for example , [1, 7, 4, 9, 2, 5] It's a Swing sequence , Because of the difference (6, -3, 5, -7, 3) It's alternating positive and negative .

contrary ,[1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] It's not a wobble sequence , The first sequence is because its first two differences are positive , The second sequence is because its last difference is zero .
Subsequence You can delete some... From the original sequence （ It can also be done without deleting ） Element to get , The remaining elements keep their original order .

Give you an array of integers nums , return nums As Swing sequence Of The length of the longest subsequence .

Example 1：

 Input ：nums = [1,7,4,9,2,5]
 Output ：6
 explain ： The whole sequence is a swing sequence , The difference between the elements is  (6, -3, 5, -7, 3) .

Example 2：

 Input ：nums = [1,17,5,10,13,15,10,5,16,8]
 Output ：7
 explain ： This sequence contains several lengths of  7  Swing sequence .
 One of them is  [1, 17, 10, 13, 10, 16, 8] , The difference between the elements is  (16, -7, 3, -3, 6, -8) .

Example 3：

 Input ：nums = [1,2,3,4,5,6,7,8,9]
 Output ：2

Tips ：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

Advanced ： Can you use O(n) Time complexity to complete this question ?

Their thinking

The law of greed

Take... For example 2 give an example , As shown in the figure below

Local optimum ： Delete nodes on monotonic slopes （ Nodes at both ends of monotonic slope are not included ）, Then this slope can have two local peaks

The best in the world ： The whole sequence has the most local peaks , So as to achieve the longest swing sequence

problem ： If you calculate the number of peaks by statistical difference, you need to consider the special cases of the leftmost and rightmost sides of the array , So for the sequence [2,5], We can assume that [2,2,5], So it has a slope , As shown in the figure below

AC Code

class Solution {
    
    public int wiggleMaxLength(int[] nums) {
    
        if (nums.length <= 1) {
    
            return nums.length;
        }
        int ans = 1;// Number of peaks , The default sequence has a peak on the far right 
        int curDiff = 0;// The difference between the current pair 
        int preDiff = 0;// The difference between the previous pair 
        for (int i = 0; i < nums.length - 1; i++) {
    
            curDiff = nums[i + 1] - nums[i];
            // Peak appears 
            if ((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)) {
    
                ans++;
                preDiff = curDiff;
            }
        }
        return ans;
    }
}