本题采用类似耐心排序的算法，通过二分查找的方式，将题目的复杂度将为（NlogN)。通过二分查找的方式可以成功地获得最长递增子序列的大小，并保证所得子序列是严格字典序的。该题的难点在于如何获得子序列中的每个元素，我们采用一个index数组记录以序号为i为结尾的最长递增子序列的长度，一个MaxInd数字记录整个数列的最长递增子序列末尾元素在veci数组中的序号，并通过倒序便利将字典序最小的最长递增子序列加入到数组res中。 #include <vector> #include <cstdio> using namespace std; int main() { //耐心排序...

class Solution { private: class UF //建立标准并查集，已进行路径压缩 { public: int count; vector<int> parents; UF(int n) { this -> count = n; parents.resize(n); for(int i = 0; i < n; ++i) parents[i] = i; } int find(int x) { if(parents[x] != x) parents[x] = find(parents[x]); return parents[x]; } bool con...