描述
给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中 按数值(注：区别于按单个字符的ASCII码值)进行比较的 字典序最小的那个）
示例1
输入：
[2,1,5,3,6,4,8,9,7]
复制
返回值：
[1,3,4,8,9]
复制
示例2
输入：
[1,2,8,6,4]
复制
返回值：
[1,2,4]
复制
说明：
其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个 按数值进行比较的字典序 最小，故答案为（1，2，4）
备注：
n \leq 10^5n≤10
5

1 \leq arr_i \leq 10^91≤arr
i
​
≤10
9

思路和心得：

1.数据为10的5次方。dp会TLE。只能二分， n * log(n)

2.记录好每个index处，LIS的最大长度

3.从右往左，找恰好达到长度的index，arr[index]放到res数组相应的位置

python3代码

#
# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
#
import bisect

class Solution:
    def LIS(self , arr ):
        # write code here
        n = len(arr)

        if not arr:
            return []
        a = []                 #辅助数组
        idx_maxLen = []        #以某个index为end的最长LIS长度
        for x in arr:
            idx = bisect.bisect_left(a, x)
            if idx == len(a):
                a.append(x)
                idx_maxLen.append(len(a))
            else:
                a[idx] = x
                idx_maxLen.append(idx + 1)

        maxLen = len(a)        #最长LIS的长度
        res = [-1 for _ in range(maxLen)]
        for i in range(n - 1, -1, -1):
            if idx_maxLen[i] == maxLen:
                res[maxLen - 1] = arr[i]
                maxLen -= 1
        return res

c++代码

class Solution 
{
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) 
    {
        // write code here
        int n = arr.size();
        if (n == 0)
            return vector<int>{};

        vector<int> a;                //辅助数组
        vector<int> idx_maxLen;        //以index为end的最长LIS的长度
        for (int x: arr)
        {
            int idx = lower_bound(a.begin(), a.end(), x) - a.begin();
            if (idx == a.size())
            {
                a.push_back(x);
                idx_maxLen.push_back((int)a.size());
            }
            else
            {
                a[idx] = x;
                idx_maxLen.push_back(idx + 1);
            }
        }

        int maxLen = (int)a.size();
        vector<int> res(maxLen, -1);
        for (int i = n - 1; i > -1; i --)
        {
            if (idx_maxLen[i] == maxLen)
            {
                res[maxLen - 1] = arr[i];
                maxLen --;
            }
        }

        return res;
    }
};

java代码

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;
        if (n == 0)
            return new int [] {};
        List<Integer> a = new ArrayList<>();
        List<Integer> idx_maxLen = new ArrayList<>();
        for (int x: arr)
        {
            int idx = binary_search_left(a, x);
            if (idx == a.size())
            {
                a.add(x);
                idx_maxLen.add(a.size());
            }
            else
            {
                a.set(idx, x);
                idx_maxLen.add(idx + 1);
            }
        }

        int maxLen = a.size();
        int res [] = new int [maxLen];
        for (int i = n - 1; i > -1; i --)
        {
            if (idx_maxLen.get(i) == maxLen)
            {
                res[maxLen - 1] = arr[i];
                maxLen --;
            }
        }
        return res;
    }

    public int binary_search_left(List<Integer> nums, int target)
    {
        int n = nums.size();
        if (n == 0)
            return 0;
        int l = 0;
        int r = n;
        while (l < r)
        {
            int mid = (l + r) / 2;
            if (nums.get(mid) >= target)
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }

}