最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

https://leetcode.cn/problems/longest-increasing-subsequence/description/

二分+贪心

样例 nums = [10,9,2,5,3,7,101,18] 逐行走：

1. x=10：tail 空，idx=0 == size → add → tail=[10]
2. x=9：binarySearch 没找到，idx=0，idx≠size → tail.set (0,9) → [9]
3. x=2：idx=0，替换 → [2]
4. x=5：idx=1 == size → add → [2,5]
5. x=3：找第一个≥3 是 5，idx=1 → set (1,3) → [2,3]
6. x=7：idx=2 == size → add → [2,3,7]
7. x=101：idx=3 == size → add → [2,3,7,101]
8. x=18：找到第一个≥18 是 101，idx=3 → set (3,18) → [2,3,7,18]

流程：

1. 数组 tail

   是有序的（升序），这是二分的前提

   • tail[0]：长度 1 的递增子序列，最小结尾
   • tail[1]：长度 2 的递增子序列，最小结尾

2. 逐个取出原数组元素 x

   • 二分在 tail 有效区间 [0, len) 找第一个 ≥ x 的位置 l

3. 两种分支

   • l == len：x 比 tail 全部有效数都大 → 可以加长 LIS，len++，x 放进 tail 末尾
   • l < len：用 x 替换 tail [l]，让这个长度的子序列结尾变得更小

class Solution {
    public int lengthOfLIS(int[] nums) {        
        int[] tail = new int[nums.length];
        int len = 0;
        for (int x : nums) {
            // 二分边界：左闭右开区间 [0, len)，只在已经有效的tail范围内查找
            int l = 0;
            int r = len;

            // 二分：找 lower_bound —— 第一个 >= x 的下标
            while (l < r) {
                // 防溢出，等价于 (l + r) / 2
                int mid = l + (r - l) / 2;
                if (tail[mid] >= x) {
                    // mid位置的值满足>=x，有可能是目标，收缩右边界
                    r = mid;
                } else {
                    // mid位置比x小，目标一定在右边
                    l = mid + 1;
                }
            }
            // 循环结束，l == r，l就是找到的位置

            if (l == len) {
                // 说明tail里所有有效数字都 < x，可以延长最长递增子序列
                tail[len++] = x;
            } else {
                // 替换：同长度的子序列，把末尾改成更小的x，给后面数字留机会
                tail[l] = x;
            }
        }
        // len就是最长递增子序列长度
        return len;
    }
}