Solution: 用二分法优化时间复杂度到O(nlgn)
建立一个数组ends，把首元素放进去，遍历整个素组：
- 如果
current num < ends[first]，替换首元素为此新元素 - 如果
current num > ends[last]，将此新元素添加到ends数组末尾(注意不覆盖原末尾元素)。 - 其他情况，
ends[first]<= current num <= ends[last]，此时用二分查找法找到第一个不小于此新元素的位置，用当前数覆盖。
以此类推直至遍历完整个nums数组，此时ends数组的长度就是我们要求的LIS的长度
- 特别注意的是ends数组的值可能不是一个真实的LIS，比如若输入数组nums为
{ 2，1 ，5 ，3 ，6，4， 8 ，9， 7}，那么算完后的ends数组为{1,3,4,7,9}，可以发现它不是一个原数组的LIS，只是长度相等而已。 - 它只是存储的对应长度LIS的最小末尾。有了这个末尾，我们就可以一个一个地插入数据。虽然最后一个7更新进去对于这组数据没有什么意义，但是如果后面再出现两个数字 8 和 9，那么就可以把8,9更新进去，得出LIS的长度为6。
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
List<Integer> LIS = new ArrayList<> ();
LIS.add (nums [0]);
for (int num : nums) {
if (num < LIS.get (0)) {
LIS.set (0, num);
} else if (num > LIS.get (LIS.size () - 1)) {
LIS.add (num);
} else {
int start = 0;
int end = LIS.size () - 1;
while (start + 1 < end) {
int middle = start + (end - start) / 2;
if (LIS.get(middle) < num) {
start = middle + 1;
} else {
end = middle;
}
}
int replaceIndex = LIS.get(start) >= num ? start : end;
LIS.set (replaceIndex, num);
}
}
return LIS.size ();
}
}
