题解 | #最长上升子序列(三)#

class Solution {
public:
    vector<int> LIS(vector<int>& arr) {
        int len = 1, n = (int)arr.size();
        if (n == 0) {
            return {};
        }
        vector<int> d(n + 1, 0), p(n);
        d[len] = arr[0];
        p[0] = 1;
        
        for (int i = 1; i < n; ++i) {
            if (arr[i] > d[len]) {
                d[++len] = arr[i];
                p[i] = len;
            } else {
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < arr[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = arr[i];
                p[i] = pos + 1;
            }
        }
         vector<int> ans(len);
        for(int i = n - 1, j = len; i>=0; i--){ 
            //逆向找到第一个满足所需大小的数
            if(p[i] == j){ 
                ans[j-1] = arr[i];//填入后继续寻找下一个数
                j = j-1;
            }
        }
        return ans;
    }
};