贪心算法实战：摆动序列与股票买卖等经典问题

2. LeetCode334. 递增的三元子序列

这道题要求判断数组中是否存在三个数呈现递增关系。虽然逻辑简单，但其中蕴含了贪心思想。

核心策略是维护两个变量 a 和 b，分别代表目前为止找到的最小值和次小值。遍历过程中，如果发现比 b 还大的数，说明找到了第三个数，直接返回 true。否则，尝试更新 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 (nums[i] > a) b = nums[i];
            else a = nums[i];
        }
        return false;
    }
};

3. LeetCode674. 最长连续递增序列

这道题要求找到最长的连续递增子数组。相比非连续子序列，这里对连续性有严格要求，因此逻辑相对直接。

只需从头到尾遍历一遍，用一个计数器记录当前连续递增的长度。一旦遇到不满足递增的情况，重置计数器。同时维护一个全局最大值 ret 即可。

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;
    }
};

4. LeetCode121. 买卖股票的最佳时机

这道题的目标是在原数组中找到两数之差最大的那两个数，即最大利润。

这里的贪心策略体现在对买入价格的动态维护上。我们只需要一次遍历，用一个变量 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;
    }
};