我將演算法學習相關的資料已經整理到了Github ：https://github.com/youngyangyang04/leetcode-master，裡面還有leetcode刷題攻略、各個型別經典題目刷題順序、思維導圖看一看一定會有所收穫，如果給你有幫助給一個star支援一下吧！
406.根據身高重建佇列題目連結：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 <= 20000 <= hi <= 10^60 <= ki < people.length題目資料確保佇列可以被重建
思路本題有兩個維度，h和k，看到這種題目一定要想如何確定一個維度，然後在按照另一個維度重新排列。
在貪心演算法：分發糖果我就強調過一次，遇到兩個維度權衡的時候，一定要先確定一個維度，再確定另一個維度。
「如果兩個維度一起考慮一定會顧此失彼」。
對於本題相信大家困惑的點是先確定k還是先確定h呢，也就是究竟先按h排序呢，還先按照k排序呢？
如果按照k來從小到大排序，排完之後，會發現k的排列並不符合條件，身高也不符合條件，兩個維度哪一個都沒確定下來。
那麼按照身高h來排序呢，身高一定是從大到小排（身高相同的話則k小的站前面），讓高個子在前面。
「此時我們可以確定一個維度了，就是身高，前面的節點一定都比本節點高！」
那麼只需要按照k為下標重新插入佇列就可以了，為什麼呢？
以圖中{5,2} 為例：
406.根據身高重建佇列
按照身高排序之後，優先按身高高的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; }};大家會發現這個n^3 是怎麼來的？
其實陣列的插入操作複雜度是O(n^2)：尋找插入元素位置O(1)，插入元素O(n^2)，因為插入元素後面的元素要整體向後移。
我們就是要模擬一個插入佇列的行為，所以不應該使用陣列，而是要使用連結串列！
連結串列的插入操作複雜度是O(n)：尋找插入元素位置O(n)，插入元素O(1)。
可以看出使用連結串列的插入效率要比普通陣列高出一個數量級！
改成連結串列之後，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()); }};大家可以把兩個版本的程式碼提交一下試試，就可以發現其差別了！
「其技巧都是確定一邊然後貪心另一邊，兩邊一起考慮，就會顧此失彼」。
最後我給出了兩個版本的程式碼，可以明顯看是使用C++中的list（底層連結串列實現）比vector（陣列）效率高得多。
「對使用某一種語言容器的使用，特性的選擇都會不同程度上影響效率」。
所以很多人都說寫演算法題用什麼語言都可以，主要體現在演算法思維上，其實我是同意的但也不同意。
對於看別人題解的同學，題解用什麼語言其實影響不大，只要題解把所使用語言特性最佳化的點講出來，大家都可以看懂，並使用自己語言的時候注意一下。
對於寫題解的同學，刷題用什麼語言影響就非常大，如果自己語言沒有學好而強調演算法和程式語言沒關係，其實是會誤傷別人的。
「這也是我為什麼統一使用C++寫題解的原因」，其實用其他語言java、python、php、go啥的，我也能寫，我的Github上也有用這些語言寫的小專案，但寫題解的話，我就不能保證把語言特性這塊講清楚，所以我始終堅持使用最熟悉的C++寫題解。
「而且我在寫題解的時候涉及語言特性，一般都會後面加上括號說明一下。沒辦法，認真負責就是我，哈哈」。
打算從頭開始打卡的錄友，可以在「演算法彙總」這裡找到歷史文章，很多錄友都在從頭打卡，你並不孤單！
我是程式設計師Carl，個人主頁：https://github.com/youngyangyang04