This is the 19th day of my participation in the Genwen Challenge

The topic of dry

If the difference between consecutive numbers alternates strictly between positive and negative numbers, a sequence of numbers is called a swing sequence. The first difference, if one exists, may be positive or negative. Sequences with only one element or two unequal elements are also considered oscillating sequences.

  • For example, [1, 7, 4, 9, 2, 5] is a swing sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative values.

  • Conversely, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not oscillating sequences, the first sequence because its first two differences are both positive, and the second sequence because its last difference is zero. Subsequences can be obtained by removing some (or none) elements from the original sequence, leaving the remaining elements in their original order.

Given an integer array nums, return the length of the oldest sequence in nums as a swing sequence.

Example 1:

Input: nums = [1,7,4,9,2,5] output: 6 explanation: the whole sequence is a swing sequence, the difference between elements is (6, -3, 5, -7, 3).Copy the code

Solution: Greed

The first thing that comes to mind is local optimal algorithms, which is greedy. Actually this problem.

We need to think about the boundary case. If the difference between the first two elements is 0 (i.e. if the two elements are equal), initialize current to 0. If the difference is not 0, initialize current to 2.

And then we go through, local optimality eventually leads to global optimality.

The code implementation is as follows:

Execution time: 72 ms, beating 96.80% of users in all JavaScript commits

Memory consumption: 37.5 MB, beating 85.60% of all JavaScript commits

/ * * *@param {number[]} nums
 * @return {number}* /
var wiggleMaxLength = function (nums) {
    let len = nums.length;
    if (len < 2) return len
    let prevdiff = nums[1] - nums[0]
    letcurrent = prevdiff ! =0 ? 2 : 1;
    for (let i = 2; i < len; ++i) {
        let diff = nums[i] - nums[i - 1];
        if (diff > 0 && prevdiff <= 0 || diff < 0 && prevdiff >= 0) {
            current++;
            prevdiff=diff
        }
    }
    return current
};
Copy the code