关注文末推广名片，即可免费获得本题测试源码！

题目来源：LeetCode300：最长递增子序列

问题抽象： 给定一个整数数组 nums，要求计算并返回该数组中 最长严格递增子序列（Longest Increasing Subsequence, LIS）的长度，满足以下核心需求：

1. 子序列定义：

   • 严格递增：序列中每个后续元素 严格大于 前一个元素（即 nums[i] > nums[j] 对所有 i > j 成立）；
   • 非连续性：子序列可从数组中 非连续 选取（通过删除部分元素实现），但必须保持原始顺序。

2. 计算目标：

   • 返回最长递增子序列的长度（整数 ≥1）；
   • 结果无需输出具体子序列（仅需长度）。

3. 输入约束：

   • 数组长度 1 ≤ n ≤ 2500，元素值 -10^4 ≤ nums[i] ≤ 10^4；
   • 时间复杂度 O(n log n)（需优于暴力法 O(n^2)）；
   • 空间复杂度 O(n)（存储动态规划状态或贪心序列）。

4. 边界处理：

   • 单元素数组：输出 1（如 [5]）；
   • 全降序数组：输出 1（如 [5,4,3] 中每个元素自成子序列）；
   • 全相同元素：输出 1（如 [2,2,2] 因非严格递增）；
   • 大值波动：如 [0,8,4,12,2,10] → 最长子序列 [0,4,10] 或 [0,2,10] → 长度 3。

输入：整数数组 nums
输出：最长递增子序列长度（整数）。

解题思路

贪心 + 二分查找（时间复杂度 O(n log n)）

1. 核心思想：维护一个数组 tail，其中 tail[i] 表示长度为 i+1 的最长递增子序列的末尾元素的最小值。该数组严格递增。
2. 遍历数组：
   • 若当前元素 num 大于 tail 的最后一个元素，则将其加入 tail 末尾（表示最长递增子序列长度增加）。
   • 否则，在 tail 中二分查找第一个大于等于 num 的位置，将其替换为 num（保证相同长度的子序列末尾元素最小）。
3. 最终结果：tail 的长度即为最长递增子序列的长度。

优势： 二分查找确保时间复杂度为 O(n log n)。 仅需一个额外数组，空间复杂度为 O(n)。

代码实现（Java版）🔥点击下载源码

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int[] tail = new int[n]; // 存储长度为 i+1 的最长递增子序列的最小末尾值
        int len = 0; // 当前 tail 的有效长度
        
        for (int num : nums) {
            // 如果 num 大于 tail 的最后一个元素，直接添加到末尾
            if (len == 0 || num > tail[len - 1]) {
                tail[len++] = num;
            } else {
                // 二分查找第一个大于等于 num 的位置
                int left = 0, right = len - 1;
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (tail[mid] < num) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                // 替换该位置的元素
                tail[left] = num;
            }
        }
        return len;
    }
}

代码说明

1. 初始化：
   • tail 数组存储不同长度递增子序列的最小末尾值，初始长度为 0。
2. 遍历数组：
   • 若当前元素 num 大于 tail 的末尾元素，则扩展 tail（长度 len++）。
   • 否则，通过二分查找在 tail[0..len-1] 中找到第一个大于等于 num 的位置 left，并替换 tail[left] = num。
3. 二分查找细节：
   • 使用左闭右闭区间 [left, right]，确保高效定位。
   • 循环终止条件 left < right 保证精确找到目标位置。
4. 返回值：
   • len 即为最长递增子序列的长度。

亮点：

• 贪心策略保证最小末尾值，减少后续元素插入的阻碍。
• 二分查找优化替换操作至 O(log n)。
• 仅需单次遍历和线性空间，满足进阶要求。

提交详情（执行用时、内存消耗）