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

LeetCode 334. 递增的三元子序列

判断数组中是否存在三个数满足 nums[i] < nums[j] < nums[k] 且 i < j < k。

这道题虽然可以用三指针暴力解，但利用贪心思想可以优化到 O(n)。核心在于维护两个变量：a 和 b。

• a 代表目前为止遇到的最小值。
• b 代表在 a 之后遇到的次小值。

当我们遍历到一个比 b 还大的数时，说明找到了第三个数，直接返回 true。否则，如果当前数比 a 小，更新 a；如果介于 a 和 b 之间，更新 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) a = nums[i];
            else if (nums[i] != a) b = nums[i];
        }
        return false;
    }
};

LeetCode 674. 最长连续递增序列

求数组中最长的连续递增子数组长度。这题相对简单，只需一次遍历。

维护一个当前连续长度 ret1 和一个最大长度 ret。如果当前元素大于前一个，计数器加一；否则重置为 1。每次迭代更新最大值即可。

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        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。对于每一天的价格，计算如果当天卖出能赚多少（p[i] - l），并更新最大利润 ret。如果当天价格更低，则更新买入价 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;
    }
};