[[436919]]

https://leetcode-cn.com/problems/queue-reconstruction-by-height

假設(shè)有打亂順序的一群人站成一個(gè)隊(duì)列，數(shù)組 people 表示隊(duì)列中一些人的屬性(不一定按順序)。每個(gè) people[i] = [hi, ki] 表示第 i 個(gè)人的身高為 hi ，前面 正好 有 ki 個(gè)身高大于或等于 hi 的人。

請(qǐng)你重新構(gòu)造并返回輸入數(shù)組 people 所表示的隊(duì)列。返回的隊(duì)列應(yīng)該格式化為數(shù)組 queue ，其中 queue[j] = [hj, kj] 是隊(duì)列中第 j 個(gè)人的屬性(queue[0] 是排在隊(duì)列前面的人)。

示例 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]]
• 解釋：
  • 編號(hào)為 0 的人身高為 5 ，沒有身高更高或者相同的人排在他前面。
  • 編號(hào)為 1 的人身高為 7 ，沒有身高更高或者相同的人排在他前面。
  • 編號(hào)為 2 的人身高為 5 ，有 2 個(gè)身高更高或者相同的人排在他前面，即編號(hào)為 0 和 1 的人。
  • 編號(hào)為 3 的人身高為 6 ，有 1 個(gè)身高更高或者相同的人排在他前面，即編號(hào)為 1 的人。
  • 編號(hào)為 4 的人身高為 4 ，有 4 個(gè)身高更高或者相同的人排在他前面，即編號(hào)為 0、1、2、3 的人。
  • 編號(hào)為 5 的人身高為 7 ，有 1 個(gè)身高更高或者相同的人排在他前面，即編號(hào)為 1 的人。
  • 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新構(gòu)造后的隊(duì)列。

示例 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

題目數(shù)據(jù)確保隊(duì)列可以被重建

思路

本題有兩個(gè)維度，h和k，看到這種題目一定要想如何確定一個(gè)維度，然后在按照另一個(gè)維度重新排列。

其實(shí)如果大家認(rèn)真做了135. 分發(fā)糖果，就會(huì)發(fā)現(xiàn)和此題有點(diǎn)點(diǎn)的像。

在135. 分發(fā)糖果我就強(qiáng)調(diào)過一次，遇到兩個(gè)維度權(quán)衡的時(shí)候，一定要先確定一個(gè)維度，再確定另一個(gè)維度。

如果兩個(gè)維度一起考慮一定會(huì)顧此失彼。

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

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

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

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

那么只需要按照k為下標(biāo)重新插入隊(duì)列就可以了，為什么呢?

以圖中{5,2} 為例：

根據(jù)身高重建隊(duì)列

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

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

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

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

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

在貪心系列開篇詞關(guān)于貪心算法，你該了解這些!中，我已經(jīng)講過了這個(gè)問題了。

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

如果沒有讀過關(guān)于貪心算法，你該了解這些!的同學(xué)建議讀一下，相信對(duì)貪心就有初步的了解了。

回歸本題，整個(gè)插入過程如下：

排序完的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]]

此時(shí)就按照題目的要求完成了重新排列。

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; 
    } 
}; 

• 時(shí)間復(fù)雜度O(nlogn + n^2)
• 空間復(fù)雜度O(n)

但使用vector是非常費(fèi)時(shí)的，C++中vector(可以理解是一個(gè)動(dòng)態(tài)數(shù)組，底層是普通數(shù)組實(shí)現(xiàn)的)如果插入元素大于預(yù)先普通數(shù)組大小，vector底部會(huì)有一個(gè)擴(kuò)容的操作，即申請(qǐng)兩倍于原先普通數(shù)組的大小，然后把數(shù)據(jù)拷貝到另一個(gè)更大的數(shù)組上。

所以使用vector(動(dòng)態(tài)數(shù)組)來insert，是費(fèi)時(shí)的，插入再拷貝的話，單純一個(gè)插入的操作就是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底層是鏈表實(shí)現(xiàn)，插入效率比vector高的多 
        for (int i = 0; i < people.size(); i++) { 
            int position = people[i][1]; // 插入到下標(biāo)為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()); 
    } 
}; 

• 時(shí)間復(fù)雜度O(nlogn + n^2)
• 空間復(fù)雜度O(n)

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

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

總結(jié)

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

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

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

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

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

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

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

對(duì)于寫題解的同學(xué)，刷題用什么語言影響就非常大，如果自己語言沒有學(xué)好而強(qiáng)調(diào)算法和編程語言沒關(guān)系，其實(shí)是會(huì)誤傷別人的。

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

而且我在寫題解的時(shí)候涉及語言特性，一般都會(huì)后面加上括號(hào)說明一下。沒辦法，認(rèn)真負(fù)責(zé)就是我，哈哈。

本文轉(zhuǎn)載自微信公眾號(hào)「代碼隨想錄」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系代碼隨想錄公眾號(hào)。