题解 | #重建二叉树#

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    int biSearch(int x, vector<int>& dp) {
        int left = 0, right = dp.size() - 1, mid;
        while(left < right) {
            mid = (left + right) / 2;
            if(dp[mid] < x)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }

    vector<int> LIS(vector<int>& arr) {
        // write code here

        if(arr.size() == 0) {
            vector<int> res;
            return res;
        }
        vector<int> len; //设置数组长度大小的动态规划辅助数组
        vector<int> dp; //用于二分划分的辅助数组
        dp.push_back(arr[0]); // 初始化
        len.push_back(1);
        for(int i = 1; i < arr.size(); i++) {
            if(arr[i] > dp[dp.size() - 1]) {
                dp.push_back(arr[i]);
                len.push_back(dp.size());
            }
            else {
                int t = biSearch(arr[i], dp); // t为att[i]在dp数组中的索引
                dp[t] = arr[i]; // 如果没有找到arr[i]，更新dp中的数值，将arr[i]压入dp
                len.push_back(t + 1); // 存储arr[i]对应的递增自序列的长度
            }
        }
        int j = dp.size(); // j == 最长递增子序列的长度
        vector<int> res(j);
        for(int i = len.size() - 1; j > 0; i--) { // 逆向找
            if(len[i] == j) {
                j--;
                res[j] = arr[i];
            }
        }
        return res;
    }
};