最长递增子序列 - 二分查找解法详解

算法核心思想

关键概念：tails 数组

• tails[i] 表示：长度为 i+1 的递增子序列中，末尾元素的最小值
• 为什么维护"最小值"？因为末尾元素越小，后续越容易接上更多元素

核心策略

对于每个新元素 num：

1. 如果 num 比 tails 中所有元素都大 → 直接添加到末尾（延长序列）
2. 如果 num 能替换某个位置 → 用二分查找找到位置并替换（保持末尾最小）

算法步骤详解

public int lengthOfLIS_Binary(int[] nums) {
    List<Integer> tails = new ArrayList<>();
    
    for (int num : nums) {
        // 1. 二分查找第一个大于等于num的位置
        int pos = Collections.binarySearch(tails, num);
        if (pos < 0) {
            pos = -(pos + 1); // 转换为插入位置
        }
        
        // 2. 判断是添加还是替换
        if (pos == tails.size()) {
            tails.add(num);      // 添加：延长序列
        } else {
            tails.set(pos, num); // 替换：保持最小末尾
        }
    }
    
    return tails.size();
}

具体例子演示

示例：nums = [10,9,2,5,3,7,101,18]

步骤	当前元素	操作	tails数组状态	说明
初始	-	-	[]	空数组
1	10	添加	[10]	第一个元素，直接添加
2	9	替换pos=0	[9]	9<10，替换位置0，保持长度1的序列末尾最小
3	2	替换pos=0	[2]	2<9，替换位置0，保持长度1的序列末尾最小
4	5	添加	[2,5]	5>2，添加到末尾，长度变为2
5	3	替换pos=1	[2,3]	3<5，替换位置1，保持长度2的序列末尾最小
6	7	添加	[2,3,7]	7>3，添加到末尾，长度变为3
7	101	添加	[2,3,7,101]	101>7，添加到末尾，长度变为4
8	18	替换pos=3	[2,3,7,18]	18<101，替换位置3，保持长度4的序列末尾最小

最终结果：长度为4

关键理解点

1. 为什么要替换而不是插入？

假设当前 tails = [2,3,7,101]，新元素是 18

选择1：插入 → [2,3,7,18,101] ❌
选择2：替换 → [2,3,7,18] ✅

为什么选择2？
- 长度4的序列：末尾是18比101更好（更容易接后续元素）
- 长度5的序列：暂时不存在，但18为后续创造了更多可能

2. tails数组的特性

• 严格递增：tails[0] < tails[1] < tails[2] < ...
• 最优性：每个位置都是该长度下的最小末尾元素
• 长度意义：tails.size() 就是最长递增子序列的长度

3. 二分查找的作用

int pos = Collections.binarySearch(tails, num);

• 找到第一个 ≥ num 的位置
• 如果 pos < 0，说明没找到，需要转换：pos = -(pos + 1)

图解理解

状态转换图

初始: []
添加10: [10]
替换9:  [9]    ← 保持长度1，但末尾更小
替换2:  [2]    ← 保持长度1，但末尾更小  
添加5:  [2,5]  ← 长度增加到2
替换3:  [2,3]  ← 保持长度2，但末尾更小
添加7:  [2,3,7] ← 长度增加到3
添加101:[2,3,7,101] ← 长度增加到4
替换18: [2,3,7,18]  ← 保持长度4，但末尾更小

决策树

遇到新元素num时：
├─ num > tails的所有元素？
│  └─ 是：添加到末尾（延长序列）
└─ 否：找到第一个≥num的位置并替换（保持最小末尾）

复杂度分析

• 时间复杂度：O(n log n)
  • 外层循环：O(n)
  • 内层二分查找：O(log n)
• 空间复杂度：O(n)
  • tails数组最多存储n个元素

常见疑问解答

Q1: 为什么tails数组的长度就是答案？

A: 因为tails[i]代表长度为i+1的序列存在，所以tails.size()就是最长序列的长度。

Q2: 替换操作会不会破坏之前的序列？

A: 不会。我们只关心长度，不关心具体的序列内容。替换是为了让后续元素更容易接上。

Q3: 这个算法能输出具体的最长子序列吗？

A: 不能直接输出。这个算法只能求长度。如果要输出具体序列，需要额外的记录过程。

小结

二分查找解法的精髓在于：

1. 贪心思想：每个长度都维护最小的末尾元素
2. 二分优化：快速找到替换位置
3. 状态压缩：用一维数组记录所有可能的长度状态

这是一个非常巧妙的算法，将O(n²)的动态规划优化到了O(n log n)！