题解 | #输出字典序最小的最长子序列#

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        // 两步：
        // 1、求最长递增子序列长度
        // 2、求最小字典序的递增子序列
        if (arr.size() <= 1)
            return arr;
        vector<int> greedyArr; // 存放由贪婪算法得到的有序子序列，但不一定满足“字典序最小”
        vector<int> maxLen; // 存放每个元素对应的最长有序子序列的长度
        // 初始化
        greedyArr.push_back(arr[0]);
        maxLen.push_back(1);
        // step1
        for (int i = 1; i < arr.size(); i++) {
            if (arr[i] > greedyArr.back()) { // 如果新元素大于当前贪婪序列的最大元素就加入
                greedyArr.push_back(arr[i]);
                maxLen.push_back(greedyArr.size());
            }
            else {
                vector<int>::iterator iter = lower_bound(greedyArr.begin(), greedyArr.end(), arr[i]);
                int idx = distance(greedyArr.begin(), iter);// 获得下标
                greedyArr[idx] = arr[i]; // arr[i]插入到当前的有序子序列中，且arr[i]对应的最长有序子序列长度即为从greedyArr开头到lower_bound的部分
                maxLen.push_back(idx+1); // 表示当前元素对应的最长有序子序列长度
            }
        }
        /*for (int i = 0; i < greedyArr.size(); i++)
            cout << greedyArr[i] << " ";
        cout << endl;
        for (int i = 0; i < maxLen.size(); i++)
            cout << maxLen[i] << " ";*/
        // step2
        vector<int> res(greedyArr.size(), 0); // 字典序最小的最长有序子序列不一定是greedyArr，但他们长度相等
        for (int i = arr.size() - 1, j = greedyArr.size(); i >= 0; i--) {
            if (maxLen[i] == j){
                res[--j] = arr[i];
            }
        }
        return res;
    }
};