题目
给你一个整数数组 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 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
题解
classSolution{publicintlengthOfLIS(int[]nums){int[]tails=newint[nums.length];intres=0;for(intnum:nums){inti=0,j=res;while(i<j){intm=(i+j)/2;if(tails[m]<num)i=m+1;elsej=m;}tails[i]=num;if(res==j)res++;}returnres;}}解析
出自：300. 最长递增子序列（动态规划 + 二分查找，清晰图解）
classSolution{publicintlengthOfLIS(int[]nums){// tails[i] 表示长度为 i+1 的递增子序列中，最小的末尾元素值// 例如：tails[0] 是长度为1的递增子序列的最小结尾int[]tails=newint[nums.length];// res 表示当前找到的最长递增子序列的长度（也是 tails 数组的有效长度）intres=0;// 遍历数组中的每一个数字for(intnum:nums){// 在 tails[0...res-1] 中二分查找第一个 >= num 的位置// i 是左边界，j 是右边界（初始为当前有效长度 res）inti=0,j=res;// 二分查找：寻找插入位置（lower bound）while(i<j){// 计算中点（避免溢出，但此处安全）intm=(i+j)/2;// 如果 tails[m] < num，说明 num 可以接在 tails[m] 后面形成更长序列// 所以目标位置在右半部分if(tails[m]<num){i=m+1;}else{// tails[m] >= num，说明可以尝试用 num 替换 tails[m] 使结尾更小// 目标位置在左半部分（包括 m）j=m;}}// 将 num 放到找到的位置 i：// - 如果 i == res，说明 num 比所有 tails 元素都大，可以扩展 LIS 长度// - 否则，用 num 替换 tails[i]，保持长度不变但让结尾更小（贪心）tails[i]=num;// 如果插入位置 i 等于原来的 res（即 j == res），说明 LIS 长度增加了if(res==j){res++;}}// 返回最长递增子序列的长度returnres;}}
