思路

先把 $1$ 直接丢到 $a$ 中。

对于每个数 $i$（$1<i\leq n$），二分出比 $i$ 小的最大值的下标。

int l = -1, r = a.size() - 1, mid;
while (l < r) {
    mid = (l + r + 1) >> 1;
    if (compare(a[mid], i)) l = mid;
    else r = mid - 1;
}

这里二分的结束条件是 $l=r$。

然后把 $i$ 插入到 $vector$ 中，从 $a.size()-2$ 倒序到 $r+1$，每次 $swap(a[i],a[i+1])$，把 $i$ 丢到下标 $r$ 的地方。

注意 $l$ 的下标必须是 $-1$，因为若 $i$ 小于 $a$ 中所有数，那么 $i$ 要扔到下标为 $0$ 的位置，那么 $r$ 二分后的值就要为 $-1$ 才行。

时间复杂度

总时间复杂度是 $O(n^2)$，询问复杂度是 $O(n\log n)$。

C++ 代码

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> a;
        int n = N;
        a.push_back(1);
        for (int i = 2; i <= n; i++) {
            int l = -1, r = a.size() - 1, mid;
            while (l < r) {
                mid = (l + r + 1) >> 1;
                if (compare(a[mid], i)) l = mid;
                else r = mid - 1;
            }
            a.push_back(i);
            for (int j = a.size() - 2; j > r; j--) swap(a[j], a[j + 1]);
        }
        return a;
    }
};

做题感觉：我是傻叉