LeetCode 406. 根据身高重建队列

题意：假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

---

思路：身高高，需求少的人往前站，所以对所有人按照身高从大到小，需求从小到大排序。遍历每个人，如果一个人前面的人数大于他需要的人数k，那么把这个人排在第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;

    }

};