🌕🌗 376. 摆动序列

难度:🌕🌗

问题描述

---

解法 1 - dp

class Solution {
    public int wiggleMaxLength(int[] nums) {
        // 思路：
        // dp[i]
        int len = nums.length;
        if(len == 1) {
            return 1;
        }
        if(len == 2) {
            if(nums[1] != nums[0]) {
                return 2;
            } else {
                return 1;
            }
        }
        // len > 2
        int pos = 0; // 保存的是上一个序列状态
        if(nums[1] > nums[0]) {
            pos = -1; // 即，如果升序，那么前面需为降序
        } else if(nums[1] < nums[0]){
            pos = 1;
        }
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        for(int i = 1; i < len; i ++) {
            if(pos == 1) {
                // 这次为降序
                if(nums[i] < nums[i - 1]) {
                    pos = -1;
                    dp[i] = dp[i - 1] + 1;
                } else {
                    // [i] >= [i - 1]
                    dp[i] = dp[i - 1];
                }
            } else if(pos == -1) {
                // 这次期望为升序
                if(nums[i] > nums[i - 1]) {
                    pos = 1;
                    dp[i] = dp[i - 1] + 1;
                } else {
                    dp[i] = dp[i - 1];
                }
            } else {
                // 上一次状态为平，判断到当前值后是否需要修改状态
                // 只有初始情况为平时，才会进入该条件，循环过程中不会出现
                if(nums[i] > nums[i - 1]) {
                    pos = 1;
                    dp[i] = dp[i - 1] + 1;
                } else if(nums[i] < nums[i - 1]) {
                    pos = -1;
                    dp[i] = dp[i - 1] + 1;
                }
            }
        }
        return dp[len - 1];
    }
}

---

输出 1

---

解法 2 - dp

class Solution {
    public int wiggleMaxLength(int[] nums) {
        // 思路：
        // dp
        // 不同于一位 dp 需要保存上一个状态，可以采用 dp[i][2] 分别记录 是升序 还是降序
        int len = nums.length;
        if(len == 1) {
            return 1;
        }
        int[][] dp = new int[len][2];
        dp[0][0] = 1; // 升序
        dp[0][1] = 1; // 降序

        for(int i = 1; i < len; i ++) {
            if(nums[i] > nums[i - 1]) {
                // 更新升序
                dp[i][0] = dp[i - 1][1] + 1;
                dp[i][1] = dp[i - 1][1];
            } else if(nums[i] < nums[i - 1]) {
                dp[i][0] = dp[i - 1][0];
                dp[i][1] = dp[i - 1][0] + 1;
            } else {
                // 既不是升序也不是降序，保存不变
                dp[i][0] = dp[i - 1][0];
                dp[i][1] = dp[i - 1][1];
            }
        }
        return Math.max(dp[len - 1][0], dp[len - 1][1]);
    }
}

---

输出 2