题解 | #最长递增子序列#

贪心+二分
（1）首先，数据范围 $n$ 为 $10^5$ ，完全的dp做法时间复杂度为 $O(n^2)$ ，肯定超时；
（2）设 $tails[i]$ 数组为当前长度为 $i + 1$ 的可能的最大递增子序列（不一定是字典序最小的！），可能的原因是该求法可以得到最大递增子序列的最大长度，但是 $tails$ 保存的未必是子序列！可以模拟看下样例，以及 $tails$ 的过程；
（3）我们贪心地希望 $tails$ 能够更长，那么希望已经构成 $tails$ 的元素更小!
（4）所以二分从 $tails$ 中找第一个大于等于 $arr[i]$ 的元素替换，如果没有就说明需要更新长度；
（5）以上做法是标准的贪心+二分求最长递增子序列的长度的做法，本题需要得到最小字典序的子序列，所以在以上基础上进行修改；
（6）我们需要记录 $curLen[i]$ 表示以当前 $arr[i]$ 元素为结尾的最长递增子序列的长度！
（7）根据 $curLen[i]$ 我们逆序地从最大长度开始遍历，即满足curLen[i] == ans条件的元素，就是长度为ans的字典序最小的方案，即可得到答案；
具体可以拿样例测一下，理解下原理；
时间复杂度： $O(n\log{n})$
空间复杂度： $O(n)$

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();
        vector<int> tail(n); //贪心的希望末尾的数字越小越好
        vector<int> curLen(n); //arr的第i个元素对应的最大递增子序列长度
        int ans = 0;
        for(int i = 0; i < n; i ++){
            int left = 0, right = ans;
            while(left < right){ //找第一个大于等于arr[i]的位置
                int mid = left + (right - left) / 2;
                if(tail[mid] >= arr[i]) right = mid;
                else left = mid + 1;
            }
            tail[left] = arr[i];
            curLen[i] = left + 1; //当前元素对应最大递增子序列的长度
            if(left == ans) ans ++;
        }
        vector<int> res(ans);
        for(int i = arr.size() - 1, j = ans; i >= 0; i --){
            if(curLen[i] == j) res[-- j] = arr[i];
        }
        return res;
    }
};