贪心算法核心思想与 LeetCode 经典例题解析

1. LeetCode 376. 摆动序列

该题要求求一个最长的摆动序列，可以从原数组中删除不符合条件的数。 思路是每次选的数字都要在有限的范围内做到尽可能的大或者尽可能的小。这是因为当我们选到最值的时候，在后面的选择中才可以有更多的选择。 我们可以通过比较相邻差值的正负来确定极值点。如果当前差值与前一个差值符号相反，说明找到了一个极值点。 注意处理连续相同元素的情况。最后的答案需要 +2，因为判断过程中没有加上两边的端点。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int left = 0;
        int right = 0;
        int sz = nums.size();
        int ret = 0;
        if (sz == 1 || (sz == 2 && (nums[0] == nums[1]))) return 1;
        if ((nums[0] == nums[sz - 1]) && (nums[0] == nums[sz / 2])) return 1;
        for (int i = 0; i < sz - 1; ++i) {
            right = nums[i + 1] - nums[i];
            if (!right) continue;
            if ((left * right) < 0) {
                ret++;
            }
            left = right;
        }
        return ret + 2;
    }
};

2. LeetCode 334. 递增的三元子序列

该题要求判断原数组里面有没有三个数是呈现递增关系的，有的话就返回 true，没有的话就返回 false。 思路是在代码编写时维护两个变量，每一次判断都在进行筛选，尽可能让前两个数变小，这样方便我们找到合适的第三个点。