贪心算法实战：摆动序列与最长递增子序列详解

题目要点 寻找最长的严格递增子序列长度。相比纯动态规划的 $O(N^2)$，我们可以利用贪心 + 二分查找优化至 $O(N \log N)$。

思路解析 维护一个数组 dp，其中 dp[i] 存储长度为 i+1 的所有递增子序列中，末尾元素的最小值。这样做的目的是为了让后续元素更容易接在后面形成更长的序列。对于每个新元素，如果它大于 dp 的最后一个元素，直接扩展；否则，用二分查找找到第一个大于等于它的位置并替换，从而保持该长度下末尾元素尽可能小。

代码实现

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        int tail = 1;
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] > dp[tail - 1]) {
                dp[tail++] = nums[i];
                continue;
            }
            int left = 0;
            int right = tail - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (dp[mid] < nums[i]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            if (nums[i] < dp[left]) {
                dp[left] = nums[i];
            }
        }
        return tail;
    }
}

3. 递增的三元子序列（Increasing Triplet Subsequence）

题目要点 判断是否存在长度为 3 的递增子序列。这是 LIS 问题的特例，只需关注是否存在三个数满足 $i < j < k$ 且 $nums[i] < nums[j] < nums[k]$。

思路解析 这里和上道题的算法原理基本一致，只是将目标长度固定为 3。当 tail 达到 3 时即可提前返回结果，无需继续计算。

代码实现

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        if (n < 3) return false;
        int[] dp = new int[3];
        int tail = 1;
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            int left = 0;
            int right = tail - 1;
            if (dp[tail - 1] < nums[i]) {
                dp[tail++] = nums[i];
            } else {
                while (left < right) {
                    int mid = (left + right) / 2;
                    if (dp[mid] < nums[i]) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
            }
            if (tail == 3) return true;
            if (nums[i] < dp[left]) {
                dp[left] = nums[i];
            }
        }
        return false;
    }
}

4. 最长连续递增序列（Longest Continuous Increasing Subsequence）

题目要点 与上一题不同，这里要求子序列必须是连续的（即子数组）。

思路解析 这实际上是贪心的最基础应用。只需遍历数组，记录当前连续递增的长度，一旦中断就重置计数器，同时更新全局最大值。时间复杂度为 $O(N)$，空间复杂度 $O(1)$。

代码实现

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if (nums.length == 0) return 0;
        int ret = 0;
        int n = nums.length;
        for (int i = 0; i < n;) {
            int j = i + 1;
            while (j < n && nums[j] > nums[j - 1]) {
                j++;
            }
            ret = Math.max(ret, j - i);
            i = j;
        }
        return ret;
    }
}

通过以上四个案例，可以看出贪心算法在处理序列问题时，核心在于如何定义'最优状态'。无论是维护极值点、最小尾部元素还是连续计数器，目标都是用最少的信息量做出正确的局部决策，从而导向全局最优。