題意：假設(shè)有打亂順序的一群人站成一個(gè)隊(duì)列杈笔。 每個(gè)人由一個(gè)整數(shù)對(duì)(h, k)表示浅碾，其中h是這個(gè)人的身高夹囚，k是排在這個(gè)人前面且身高大于或等于h的人數(shù)部念。 編寫一個(gè)算法來(lái)重建這個(gè)隊(duì)列舞痰。
思路：身高高土榴，需求少的人往前站，所以對(duì)所有人按照身高從大到小响牛，需求從小到大排序玷禽。遍歷每個(gè)人赫段，如果一個(gè)人前面的人數(shù)大于他需要的人數(shù)k，那么把這個(gè)人排在第k位矢赁。這題有中間的插入糯笙，用雙向鏈表比較好。正好又熟悉了一下STL里面list的用法撩银。
push_back() / push_front()
pop_back() / pop_front()
insert(iterator, val)
advance(iterator, step)?
C++代碼：
class?Solution?{
public:
????struct?node{
????????int?h,?k;
????????node(int?h,?int?k)?:?h(h),?k(k){}
????};
????static?bool?cmp(node?a,?node?b){
????????if(a.h?==?b.h)?return?a.k?<?b.k;
????????return?a.h?>?b.h;
????}
????vector<vector<int>>?reconstructQueue(vector<vector<int>>&?people)?{
????????vector<node>?vec;
????????for(int?i?=?0;?i?<?people.size();?i++){
????????????vec.push_back(node(people[i][0],?people[i][1]));
????????}
????????sort(vec.begin(),?vec.end(),?cmp);
????????list<node>?lst;
????????for(int?i?=?0;?i?<?vec.size();?i++){
????????????if(lst.size()?==?0)?lst.push_back(vec[i]);
????????????else?if(lst.size()?==?vec[i].k){
????????????????lst.push_back(vec[i]);
????????????}
????????????else?if(lst.size()?>?vec[i].k){
????????????????auto?it?=?lst.begin();
????????????????advance(it,?vec[i].k);?
????????????????lst.insert(it,?vec[i]);
????????????}
????????}
????????vector<vector<int>>?res;
????????for(auto?it?=?lst.begin();?it?!=?lst.end();?it++){
????????????vector<int>?v?{it->h,?it->k};
????????????res.push_back(v);
????????}
????????return?res;
????}
};
