贪心算法实战：摆动序列与股票买卖

贪心算法核心思路

贪心算法的核心在于局部最优推导全局最优，但这往往需要经验积累。通过几道经典题目，我们可以更直观地理解这种策略在实际编码中的应用。

LeetCode 376. 摆动序列

这道题要求找出最长的摆动子序列。所谓摆动序列，就是相邻元素的差值正负交替。为了得到最长序列，我们在每一步选择时都应尽可能让当前极值点成为波峰或波谷，这样后续的选择空间才最大。

看上面的图，假设在 c 和 d 之间选了一个非极值点 x1，那么后续可能就无法满足摆动条件了。这就是为什么我们要选极值点的原因。代码实现上，我们可以通过比较相邻元素的差值符号变化来判断极值点位置。

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; // 加上首尾两个端点
    }
};

注意这里 ret + 2 是因为循环统计的是中间的变化次数，需要补上首尾两个端点。

LeetCode 334. 递增的三元子序列

题目要求判断数组中是否存在三个数呈递增关系。这其实是一个典型的贪心应用：我们不需要找到具体的哪三个数，只需要维护两个变量 a 和 b，分别代表找到的最小值和次小值。只要遍历过程中发现比 b 大的数，就说明存在三元组。

关键在于每次更新时都要尽量让 a 和 b 变小，这样更容易遇到符合条件的第三个数。

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int a = nums[0];
        int b = INT_MAX;
        int sz = nums.size();
        
        for (int i = 1; i < sz; ++i) {
            if (nums[i] > b) return true;
            if (a > nums[i]) a = nums[i];
            else if (nums[i] != a) b = nums[i];
            else continue;
        }
        return false;
    }
};

LeetCode 674. 最长连续递增序列

这道题相对简单，要求找到最长的连续递增子数组。只需从头到尾遍历一次，记录当前连续长度和最大长度即可。

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int ret = 1;
        int ret1 = 1;
        int sz = nums.size();
        
        for (int i = 0; i < sz - 1; ++i) {
            if (nums[i + 1] > nums[i]) ret1++;
            else ret1 = 1;
            if (ret1 > ret) ret = ret1;
        }
        return ret;
    }
};

LeetCode 121. 买卖股票的最佳时机

这道题本质是求两数之差的最大值。贪心策略体现在不断更新历史最低价 l，用当前价格减去它来尝试获取最大利润。

class Solution {
public:
    int maxProfit(vector<int>& p) {
        int sz = p.size();
        int ret = 0;
        int l = INT_MAX; // 记录买入价
        
        for (int i = 0; i < sz; ++i) {
            if (l < p[i]) ret = max(ret, p[i] - l);
            if (l > p[i]) l = p[i];
        }
        return ret;
    }
};

这里的贪心之处在于 l 一直在动态更新，确保我们始终基于当前的最低成本来计算收益。