406. 根据身高重建队列

思路

先安置较高的，再安置较矮的。

由于每个人只能看与自己同高或更高的。也就是说较高者的k值，不受较矮者的影响。

那么，我们如果先按照身高进行排序之后，每次取出输入序列中的最高者。

那么已安排序列中所有人的身高一定都比当前输入者的身高要高。那么，输入者的k值一定放到已安排序列中第k个一定是符合顺序的。

原题输入: [7,0],[4,4],[7,1],[5,0],[6,1],[5,2]

根据身高排个序，得到输入序列 [7,0],[7,1],[6,1],[5,0],[5,2],[4,4]

已安排序列: [ ]

• 放入[7,0],根据k值放置
  输入序列: [7,1],[6,1],[5,0],[5,2],[4,4]
  安排序列: [7,0]

• 放入[7,1]
  输入序列: [6,1],[5,0],[5,2],[4,4]
  安排序列: [7,0],[7,1]

• 放入[6,1],与已经存在的[7,1]存在冲突，由于7 > 6, 因此可以将[7,1]往后挪
  输入序列: [5,0],[5,2],[4,4]
  安排序列: [7,0],[6,1],[7,1]

• 放入 [5,0], 同上冲突, 由于所有数都比[5,0]大,我们可以将它们任意挪动，而不影响它们的k值
  输入序列: [5,2],[4,4]
  安排序列: [5,0], [7,0],[6,1],[7,1]

• 放入 [5,2],
  输入序列: [4,4]
  安排序列: [5,0],[7,0],[5,2],[6,1],[7,1]

• 放入[4,4]
  输入序列: []
  安排序列: [5,0],[7,0],[5,2],[6,1],[4,4],[7,1],

实现

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        std::sort(people.begin(), people.end(),
        [&](const auto &lhs, const auto& rhs){
            // h相等, k降序
            // h不等, h升序
            return lhs[0] == rhs[0] ? lhs[1] < rhs[1] : lhs[0] > rhs[0];
        });

 
        vector<vector<int>> tmp;
        for(int i = 0; i != people.size();++i){
            tmp.insert(tmp.begin() + people[i][1], people[i]);
        }
        return tmp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18