Leetcode|中等|两维度贪心|406. 根据身高重建队列（固定1维贪心再贪心另1维）

1 两维度贪心算法（链表版）

【贪心】：先对两维度中的(第一维)身高降序排序，其中等高者，(第二维)其前方人数k少的排前面

局部最优

：优先将高个子的people按其前方人数k来插入，这样后面低个子往前插入时不破坏高个子属性

全局最优

：最后都做完插入操作，整个队列满足题目队列属性

排序完的people：

[[7,0], [7,1], [6,1], [5,0], [5,2]，[4,4]]

插入的过程：

插入[7,0]：[[7,0]]

插入[7,1]：[[7,0],[7,1]]

插入[6,1]：[[7,0],[6,1],[7,1]]

插入[5,0]：[[5,0],[7,0],[6,1],[7,1]]

插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]

插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

本题策略：

高个子h大的优先排前，同等个子下，k小的优先
后面低个子插入到链表前k_i的位置（不破坏低个子前面高个子的属性）

class Solution {
private:
    static bool cmp(vector<int>& a, vector<int>& b) {
        if (a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        // 1.高个子h大的优先，同等个子k小的优先
        sort(people.begin(), people.end(), cmp);
        list<vector<int>> lst;          // 链表提高插入效率
        lst.emplace_back(people[0]);
        for (int i = 1; i < people.size(); i++) { 
            auto it = lst.begin();
            advance(it, people[i][1]);  // 将链表起始迭代器向后推进k_i个
            // 2.后面低个子插入到链表前k_i的位置（不破坏低个子前面高个子的属性）
            lst.insert(it, people[i]);
        }
        // 3.list转vector
        return vector<vector<int>> (lst.begin(), lst.end());
    }
};

复制

致谢

图片来源于「代码随想录」公众号，欢迎大家关注这位大佬的公号