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

二、力扣 300. 最长递增子序列

1. 题目解析

这是经典的动态规划问题，但使用贪心策略配合二分查找可以将时间复杂度优化到 O(n log n)。

2. 算法原理

维护一个数组 dp，其中 dp[i] 存储长度为 i+1 的递增子序列的最小末尾元素。遍历原数组时，如果当前元素大于 dp 的末尾，直接扩展；否则，用二分查找找到第一个大于等于当前元素的位置并替换，这样能保持后续元素有更大的增长空间。

3. 代码实现

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

三、力扣 334. 递增的三元子序列

1. 题目解析

这道题是 LIS 问题的简化版，只需判断是否存在长度为 3 的递增子序列即可。

2. 算法原理

逻辑与上一题基本一致，只是当 tail 达到 3 时，说明找到了满足条件的三元组，可以直接返回 true。

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

四、力扣 674. 最长连续递增序列

1. 题目解析

这是 LIS 的最简单版本，要求子数组必须连续。因此不需要复杂的 DP 或二分查找。

2. 算法原理

只需一次线性扫描，比较相邻元素。如果当前元素大于前一个，计数器增加；否则重置起始位置。

3. 代码实现

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        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;
    }
}