贪心算法实战：从摆动序列到股票买卖的解题思路

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

题目要求判断是否存在长度为 3 的递增子序列。虽然看似需要三层循环，但利用贪心思想可以将复杂度降为 O(n)。

思路分析

维护两个变量 a 和 b，分别代表目前为止找到的最小值和次小值。遍历数组时，如果当前数大于 b，则找到了第三个数，返回 true。否则，尝试更新 a 或 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;
    }
};

3. LeetCode 674. 最长连续递增序列

此题逻辑较为直接，要求子数组必须连续。只需一次遍历，统计当前连续递增的长度，并更新全局最大值即可。

思路分析

使用 ret 记录历史最大长度，ret1 记录当前连续长度。遇到递增则 ret1++，否则重置为 1。每次迭代后比较并更新 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. LeetCode 121. 买卖股票的最佳时机

目标是找到两数之差的最大值。这可以通过一次遍历完成，关键在于动态维护历史最低价格。

思路分析

贪心策略体现为：只要当前价格高于历史最低价，就计算利润并尝试更新最大利润；同时不断更新历史最低价。这样保证了我们在卖出时，买入价一定是之前的最低点。

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