最长摆动序列[贪心练习]

前言

贪心/动态规划/单调栈，都是考察逻辑能力的一类高级题目，这些题需要分析，需要较好的变通能力。

一、最长摆动序列

二、贪心算法

1、贪心需要满足的条件

最优子结构：规模较大的问题的解由规模较小的子问题的解组成，规模较大的问题的解只由其中一个规模较小的子问题的解决定；
无后效性：后面阶段的求解不会修改前面阶段已经计算好的结果；
贪心选择性质：从局部最优解可以得到全局最优解。

注：其中对无后效性的把握尤为重要。贪心算法就是做出当前状态下的最优选择认为就可以解决问题。

2、思路分析

该题，只需要顺序找到峰和谷就行了，以高峰低谷作为摆动的节点，其体系那贪最值问题。

3、code

package everyday.greed;

public class WiggleMaxLength {
    
    /* target：找最长摆动子序列。 把非峰/谷元素删掉即可，但是这里只需要统计最长摆动序列的长度，而不是最长摆动序列的元素，所以只计算峰/谷节点数，相当于变相删了其他非峰/谷节点。 */
    public int wiggleMaxLength(int[] nums) {
    
        if (nums.length < 2) return nums.length;
        // 核心：只要最高峰/最低谷的元素，即最大最小值，摆动起来。
        int curDiff = 0, preDiff = 0, ans = 1;
        for (int i = 0; i < nums.length - 1; i++) {
    
            curDiff = nums[i + 1] - nums[i];
            // 计算峰 || 计算谷
            if (curDiff > 0 && preDiff <= 0 || curDiff < 0 && preDiff >= 0) {
    
                ++ans;
                preDiff = curDiff;
            }
        }
        return ans;
    }
}

总结

1）贪心练习。

参考文献

[1] LeetCode 最长摆动序列