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

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

判断原数组里是否存在三个数呈现递增关系。解法相对直接，维护两个变量分别记录目前为止遇到的最小值和次小值。

这里体现了贪心思想：每一次判断都在筛选，尽可能让 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. 最长连续递增序列

从原数组里找到最长的递增子数组，且要求是连续的。

从头到尾遍历一遍，记录当前的递增长度，同时更新最大长度即可。

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. 买卖股票的最佳时机

在原数组里面找到两数之差最大的那两个数，即最大利润。

一次遍历，用一个变量 l 不断更新历史最低价，这样就能算出当前价格能带来的最大收益。贪心体现在 l 一直在动态更新，确保买入成本最低。

class Solution {
public:
    int maxProfit(vector<int>& p) {
        int sz = p.size();
        int ret = 0;
        int ret1 = 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;
    }
};