[[436919]]

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. 分發(fā)糖果，就會發(fā)現和此題有點點的像。

在135. 分發(fā)糖果我就強調過一次，遇到兩個維度權衡的時候，一定要先確定一個維度，再確定另一個維度。

如果兩個維度一起考慮一定會顧此失彼。

對于本題相信大家困惑的點是先確定k還是先確定h呢，也就是究竟先按h排序呢，還先按照k排序呢?

如果按照k來從小到大排序，排完之后，會發(fā)現k的排列并不符合條件，身高也不符合條件，兩個維度哪一個都沒確定下來。

那么按照身高h來排序呢，身高一定是從大到小排(身高相同的話則k小的站前面)，讓高個子在前面。

此時我們可以確定一個維度了，就是身高，前面的節(jié)點一定都比本節(jié)點高!

那么只需要按照k為下標重新插入隊列就可以了，為什么呢?

以圖中{5,2} 為例：

根據身高重建隊列

按照身高排序之后，優(yōu)先按身高高的people的k來插入，后序插入節(jié)點也不會影響前面已經插入的節(jié)點，最終按照k的規(guī)則完成了隊列。

所以在按照身高從大到小排序后：

• 局部最優(yōu)：優(yōu)先按身高高的people的k來插入。插入操作過后的people滿足隊列屬性
• 全局最優(yōu)：最后都做完插入操作，整個隊列滿足題目隊列屬性

局部最優(yōu)可推出全局最優(yōu)，找不出反例，那就試試貪心。

一些同學可能也會疑惑，你怎么知道局部最優(yōu)就可以推出全局最優(yōu)呢?有數學證明么?

在貪心系列開篇詞關于貪心算法，你該了解這些!中，我已經講過了這個問題了。

刷題或者面試的時候，手動模擬一下感覺可以局部最優(yōu)推出整體最優(yōu)，而且想不到反例，那么就試一試貪心，至于嚴格的數學證明，就不在討論范圍內了。

如果沒有讀過關于貪心算法，你該了解這些!的同學建議讀一下，相信對貪心就有初步的了解了。

回歸本題，整個插入過程如下：

排序完的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(可以理解是一個動態(tài)數組，底層是普通數組實現的)如果插入元素大于預先普通數組大小，vector底部會有一個擴容的操作，即申請兩倍于原先普通數組的大小，然后把數據拷貝到另一個更大的數組上。

所以使用vector(動態(tài)數組)來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)

大家可以把兩個版本的代碼提交一下試試，就可以發(fā)現其差別了!

關于本題使用數組還是使用鏈表的性能差異，我在貪心算法：根據身高重建隊列(續(xù)集)中詳細講解了一波

總結

關于出現兩個維度一起考慮的情況，我們已經做過兩道題目了，另一道就是135. 分發(fā)糖果。

其技巧都是確定一邊然后貪心另一邊，兩邊一起考慮，就會顧此失彼。

這道題目可以說比135. 分發(fā)糖果難不少，其貪心的策略也是比較巧妙。

最后我給出了兩個版本的代碼，可以明顯看是使用C++中的list(底層鏈表實現)比vector(數組)效率高得多。

對使用某一種語言容器的使用，特性的選擇都會不同程度上影響效率。

所以很多人都說寫算法題用什么語言都可以，主要體現在算法思維上，其實我是同意的但也不同意。

對于看別人題解的同學，題解用什么語言其實影響不大，只要題解把所使用語言特性優(yōu)化的點講出來，大家都可以看懂，并使用自己語言的時候注意一下。

對于寫題解的同學，刷題用什么語言影響就非常大，如果自己語言沒有學好而強調算法和編程語言沒關系，其實是會誤傷別人的。

這也是我為什么統(tǒng)一使用C++寫題解的原因，其實用其他語言java、python、php、go啥的，我也能寫，我的Github上也有用這些語言寫的小項目，但寫題解的話，我就不能保證把語言特性這塊講清楚，所以我始終堅持使用最熟悉的C++寫題解。 

而且我在寫題解的時候涉及語言特性，一般都會后面加上括號說明一下。沒辦法，認真負責就是我，哈哈。

本文轉載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關注。轉載本文請聯系代碼隨想錄公眾號。