描述


给定数组 arr ，设长度为 n ，输出 arr 的最长上升子序列。（如果有多个答案，请输出其中 按数值(注：区别于按单个字符的ASCII码值)进行比较的 字典序最小的那个）

数据范围：0 \le n \le 200000 , 0 \le arr_i \le 10000000000≤n≤200000,0≤arri≤1000000000
要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)
 

示例1

输入： 
[2,1,5,3,6,4,8,9,7]
返回值： 
[1,3,4,8,9]
可能会遇到的疑问解释：
  1，替换的主要作用就是，找到arr当前的元素，在temp中的位置，从而确定它的长度。 比如temp数组元素为[2,4,6], 
   而arr中当前元素为5，那temp中第一个大于5的元素就是6，那5的长度就是3 。同时替换掉后，也能不影响后续元素位置的
   判定。
 2，因为当arr数组的当前元素  ，小于temp数组的最后一个元素时，只是替换temp中的元素，而不增加，因此不更新max值
  3，要从后往前遍历，比如arr数组为[2,5,3,6,4] ,对应的元素长度 len数组为[1,2,2,3,3] ,根据题意得到的 字典序最小的 最长子序列应该是[2,3,4] ，
    而通过从后往前遍历就可以实现，原理是，后面小的元素会替换前面大的元素，所以相同长度下，一定是后面的元素更小。

代码注释
  
import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        // write code here
        int n = arr.length;
              // 定义一个数组，用来维护一个当前最长的子序列
        int[] temp =new int[n];
               // 定义一个数组len，用来记录每个元素当前的长度
        int[] len = new int[n];
                // 定义一个变量 max ，用来记录temp中最长的子序列长度
        int max =0;
        for(int i=0;i<n;i++){
                   // 当temp为空时，先放入arr中第一个元素， 有了第一个元素后， 只有当arr中元素大于temp
                      // 才把其添加到temp数组中
                            // max-1 是因为，每次temp中添加完数据，记录最大值的max要加一，比如temp为空时，
                               // 添加一个数据，max变为1，但其实添加的元素在temp中下标为0，temp[0]才是当
                                  // 前temp中最后一个元素
            if(i==0 || temp[max-1]<arr[i]){
                          // 每次添加一个数组到temp数组中，就给max加一
                temp[max++]=arr[i];
                              // 记录长度的len数组，就记录当前arr数组元素的长度
                len[i]= max;
                          
            }else{
                          // 如果arr数组中当前元素小于temp中最后一个元素，那就找到temp中第一个大于arr数组的元素，
                            // 然后将其替换掉（看上面疑问解释1）
                int index = search(temp,max,arr[i]);
                temp[index]= arr[i];
                             // 替换后，更新arr数组中当前元素的长度。 但是不更新 max 值（看上面疑问解释2 ）
                len[i]=index +1;
            }
        }
             // 最后用一个新的数组，从后往前遍历arr数组，拿到字典序最小的 最长子序列（看上面疑问解释3 ）
        int[] res = new int[max];
        for(int i=n-1;i>=0;i--){
                    // 当max与当前元素的长度相同，就把它放入res数组中
            if(len[i] == max)
                     // 长度比下标大一，所以要先减一
            res[--max] = arr[i];
        }
        return res;
    }
    public int search(int[] temp,int max,int arrI){
        int left = 0;
        int right = max-1;
        while(left<right){
            int mid = left+(right-left)/2;
            if(temp[mid]>= arrI){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return left;
    }
}