题意: 见题面。
题解:
考虑本题可以使用二分的原因,假设初始有两个哨兵$min$和$max$,其中$min$大于所有元素,$max$大于所有元素。
此时我们开始二分$x$可以存放的位置:
$if(a[mid] < x)$ 此时更新 $l = mid$,表示$mid$这个位置的右边放$x$是合法的,继续向右二分
$else → (a[mid] > x)$ 那么此时更新$r=mid-1$,表示$mid$这个位置右边放$x$是不合法的,继续向左二分
为什么合法向右,不合法向左呢?
-
如果一直不合法,那么就可以向左直到所有元素的前面,哨兵$min$一定小于$x$,所以此时可以将$x$放在哨兵和第一个元素之间。
-
如果一直合法,那么就可以向右直到所有元素的后面,哨兵$max$一定大于$x$,所以此时可以将$x$放在最后一个元素和哨兵之间。
如下为例:
如果$a[mid] > x$,则看$a[mid-1]$是否小于$x$,如果小于$x$,则可以插在$mid-1$和$mid$之间,否则继续看$mid-2…$
如果到了首元素$a[1]$仍然不满足,那么可以将$x$加入到$a[1]$左边,所以二分如果一直不合法,则可以一直往左,因为有一个$min$可以保证我们一直不合法就可以加入$a[1]$左边。
向右同样道理:
如果$a[mid] < x$,则看$a[mid+1]$是否大于$x$,如果大于$x$,则可以插在$mid$和$mid+1$之间,否则继续看$mid+2…$
如果到了尾元素$a[last]$仍然不满足,那么可以将$x$加入到$a[last]$右边,所以二分如果一直合法,则可以一直往右,因为有一个$max$可以保证我们一直合法就可以加入$a[last]$右边。
代码:
class Solution {
public:
vector<int> specialSort(int N) {
vector<int> res(1, 1);
for(int i = 2; i <= N; ++i) {
int l = 0, r = (int)res.size() - 1;
while(l < r) {
int mid = l + r + 1 >> 1;
if(compare(res[mid], i)) l = mid;
else r = mid - 1;
}
res.push_back(i);
for(int j = (int)res.size() - 2; j > r; --j) swap(res[j], res[j + 1]);
if(compare(i, res[r])) swap(res[r], res[r + 1]);
}
return res;
}
};