376.摆动序列.md

376.摆动序列

/*
 * @lc app=leetcode.cn id=376 lang=typescript
 *
 * [376] 摆动序列
 */

// @lc code=start
function wiggleMaxLength(nums: number[]): number {}
// @lc code=end

解法 1: 动态规划

• dp 表示 0 ~ i 的最长摆动序列
• l 表示当前 dp 的长度
• dp[l-1]>dp[l-2]: nums[i]<dp[l-1] ? dp.push(nums[i]) : dp[l-1]=nums[i]
• dp[l-1]<dp[l-2]: nums[i]>dp[l-1] ? dp.push(nums[i]) : dp[l-1]=nums[i]

function wiggleMaxLength(nums: number[]): number {
  let dp = [nums[0]]
  for (let i = 1; i < nums.length; i++) {
    const l = dp.length
    if (
      (l === 1 && nums[i] !== dp[0]) ||
      (dp[l - 1] > dp[l - 2] && nums[i] < dp[l - 1]) ||
      (dp[l - 1] < dp[l - 2] && nums[i] > dp[l - 1])
    ) {
      dp.push(nums[i])
    } else {
      dp[l - 1] = nums[i]
    }
  }
  return dp.length
}

Case

test.each([
  { input: { nums: [1, 7, 4, 9, 2, 5] }, output: 6 },
  { input: { nums: [1, 17, 5, 10, 13, 15, 10, 5, 16, 8] }, output: 7 },
  { input: { nums: [1, 2, 3, 4, 5, 6, 7, 8, 9] }, output: 2 },
  { input: { nums: [0, 0] }, output: 1 },
])('input: nums = $input.nums', ({ input: { nums }, output }) => {
  expect(wiggleMaxLength(nums)).toEqual(output)
})