如何根據身高重建隊列，你學會了嗎？
https://leetcode-cn.com/problems/queue-reconstruction-by-height
假設有打亂順序的一群人站成一個隊列，數組 people 表示隊列中一些人的屬性(不一定按順序)。每個 people[i] = [hi, ki] 表示第 i 個人的身高為 hi ，前面 正好 有 ki 個身高大于或等于 hi 的人。
請你重新構造并返回輸入數組 people 所表示的隊列。返回的隊列應該格式化為數組 queue ，其中 queue[j] = [hj, kj] 是隊列中第 j 個人的屬性(queue[0] 是排在隊列前面的人)。
示例 1：
- 輸入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
- 輸出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
- 解釋：
- 編號為 0 的人身高為 5 ，沒有身高更高或者相同的人排在他前面。
- 編號為 1 的人身高為 7 ，沒有身高更高或者相同的人排在他前面。
- 編號為 2 的人身高為 5 ，有 2 個身高更高或者相同的人排在他前面，即編號為 0 和 1 的人。
- 編號為 3 的人身高為 6 ，有 1 個身高更高或者相同的人排在他前面，即編號為 1 的人。
- 編號為 4 的人身高為 4 ，有 4 個身高更高或者相同的人排在他前面，即編號為 0、1、2、3 的人。
- 編號為 5 的人身高為 7 ，有 1 個身高更高或者相同的人排在他前面，即編號為 1 的人。
- 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新構造后的隊列。
示例 2：
- 輸入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
- 輸出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
提示：
- 1 <= people.length <= 2000
- 0 <= hi <= 10^6
- 0 <= ki < people.length
題目數據確保隊列可以被重建
思路
本題有兩個維度，h和k，看到這種題目一定要想如何確定一個維度，然后在按照另一個維度重新排列。
其實如果大家認真做了135. 分發糖果，就會發現和此題有點點的像。
在135. 分發糖果我就強調過一次，遇到兩個維度權衡的時候，一定要先確定一個維度，再確定另一個維度。
如果兩個維度一起考慮一定會顧此失彼。
對于本題相信大家困惑的點是先確定k還是先確定h呢，也就是究竟先按h排序呢，還先按照k排序呢?
如果按照k來從小到大排序，排完之后，會發現k的排列并不符合條件，身高也不符合條件，兩個維度哪一個都沒確定下來。
那么按照身高h來排序呢，身高一定是從大到小排(身高相同的話則k小的站前面)，讓高個子在前面。
此時我們可以確定一個維度了，就是身高，前面的節點一定都比本節點高!
那么只需要按照k為下標重新插入隊列就可以了，為什么呢?
以圖中{5,2} 為例：
根據身高重建隊列
按照身高排序之后，優先按身高高的people的k來插入，后序插入節點也不會影響前面已經插入的節點，最終按照k的規則完成了隊列。
所以在按照身高從大到小排序后：
- 局部最優：優先按身高高的people的k來插入。插入操作過后的people滿足隊列屬性
- 全局最優：最后都做完插入操作，整個隊列滿足題目隊列屬性
局部最優可推出全局最優，找不出反例，那就試試貪心。
一些同學可能也會疑惑，你怎么知道局部最優就可以推出全局最優呢?有數學證明么?
在貪心系列開篇詞關于貪心算法，你該了解這些!中，我已經講過了這個問題了。
刷題或者面試的時候，手動模擬一下感覺可以局部最優推出整體最優，而且想不到反例，那么就試一試貪心，至于嚴格的數學證明，就不在討論范圍內了。
如果沒有讀過關于貪心算法，你該了解這些!的同學建議讀一下，相信對貪心就有初步的了解了。
回歸本題，整個插入過程如下：
排序完的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]]
此時就按照題目的要求完成了重新排列。
C++代碼如下：
- // 版本一
- class Solution {
- public:
- static bool cmp(const vector<int> a, const vector<int> b) {
- if (a[0] == b[0]) return a[1] < b[1];
- return a[0] > b[0];
- }
- vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
- sort (people.begin(), people.end(), cmp);
- vector<vector<int>> que;
- for (int i = 0; i < people.size(); i++) {
- int position = people[i][1];
- que.insert(que.begin() + position, people[i]);
- }
- return que;
- }
- };
- 時間復雜度O(nlogn + n^2)
- 空間復雜度O(n)
但使用vector是非常費時的，C++中vector(可以理解是一個動態數組，底層是普通數組實現的)如果插入元素大于預先普通數組大小，vector底部會有一個擴容的操作，即申請兩倍于原先普通數組的大小，然后把數據拷貝到另一個更大的數組上。
所以使用vector(動態數組)來insert，是費時的，插入再拷貝的話，單純一個插入的操作就是O(n^2)了，甚至可能拷貝好幾次，就不止O(n^2)了。
改成鏈表之后，C++代碼如下：
- // 版本二
- class Solution {
- public:
- // 身高從大到小排（身高相同k小的站前面）
- static bool cmp(const vector<int> a, const vector<int> b) {
- if (a[0] == b[0]) return a[1] < b[1];
- return a[0] > b[0];
- }
- vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
- sort (people.begin(), people.end(), cmp);
- list<vector<int>> que; // list底層是鏈表實現，插入效率比vector高的多
- for (int i = 0; i < people.size(); i++) {
- int position = people[i][1]; // 插入到下標為position的位置
- std::list<vector<int>>::iterator it = que.begin();
- while (position--) { // 尋找在插入位置
- it++;
- }
- que.insert(it, people[i]);
- }
- return vector<vector<int>>(que.begin(), que.end());
- }
- };
- 時間復雜度O(nlogn + n^2)
- 空間復雜度O(n)
大家可以把兩個版本的代碼提交一下試試，就可以發現其差別了!
關于本題使用數組還是使用鏈表的性能差異，我在貪心算法：根據身高重建隊列(續集)中詳細講解了一波
總結
關于出現兩個維度一起考慮的情況，我們已經做過兩道題目了，另一道就是135. 分發糖果。
其技巧都是確定一邊然后貪心另一邊，兩邊一起考慮，就會顧此失彼。
這道題目可以說比135. 分發糖果難不少，其貪心的策略也是比較巧妙。
最后我給出了兩個版本的代碼，可以明顯看是使用C++中的list(底層鏈表實現)比vector(數組)效率高得多。
對使用某一種語言容器的使用，特性的選擇都會不同程度上影響效率。
所以很多人都說寫算法題用什么語言都可以，主要體現在算法思維上，其實我是同意的但也不同意。
對于看別人題解的同學，題解用什么語言其實影響不大，只要題解把所使用語言特性優化的點講出來，大家都可以看懂，并使用自己語言的時候注意一下。
對于寫題解的同學，刷題用什么語言影響就非常大，如果自己語言沒有學好而強調算法和編程語言沒關系，其實是會誤傷別人的。
這也是我為什么統一使用C++寫題解的原因，其實用其他語言java、python、php、go啥的，我也能寫，我的Github上也有用這些語言寫的小項目，但寫題解的話，我就不能保證把語言特性這塊講清楚，所以我始終堅持使用最熟悉的C++寫題解。
而且我在寫題解的時候涉及語言特性，一般都會后面加上括號說明一下。沒辦法，認真負責就是我，哈哈。
本文轉載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關注。轉載本文請聯系代碼隨想錄公眾號。
