分析

代码：

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {

        vector<int> res;
        /*给定样例是N >= 1， 说明有一个元素肯定是1*/
        res.push_back(1);
        for(int i = 2;i <= N; ++i)
        {
            int l = 0, r = res.size() - 1;
            while(l < r)
            {
                int mid = l + r + 1>> 1;
                /*如果按照题目中的条件找到了小于i的数，插进去*/
                if(compare(res[mid], i))l = mid;
                else r = mid - 1;
            }
          //  cout << r << endl;
            res.push_back(i);
            for(int j = res.size() - 2; j > r; --j)
                swap(res[j], res[j + 1]);
            /*如果所有的数都大于当前判断的数i*/
            if(compare(i, res[r]))swap(res[r], res[r + 1]);
        }
        /*要返回res*/
        return res;
    }
};