❶ 「leetcode」406.根據身高重建隊列【貪心演算法】詳細圖解
「leetcode」406.根據身高重建隊列的貪心演算法解析如下：
解題思路： 排序：首先，我們需要對給定的人數組 people 按照身高 h 從高到低進行排序。這是貪心策略的第一步，確保在插入過程中，已經插入隊列中的人身高都不低於當前要插入的人。 插入：排序後，我們按照每個人的 k 值依次將每個人插入到隊列中的正確位置。由於鏈表在插入操作上具有 O 的復雜度，因此選擇鏈表作為數據結構來存儲隊列。
具體步驟：1. 排序：將 people 數組按照身高 h 降序排列，如果身高相同，則按照 k 升序排列。2. 插入：創建一個空的鏈表作為隊列。遍歷排序後的 people 數組，對於每個人 [hi, ki]，將其插入到鏈表的第 ki 個位置。由於鏈表支持 O 復雜度的插入操作，因此這一步可以高效完成。3. 輸出結果：最後，將鏈表轉換為數組形式，即為重建後的隊列。
關鍵點： 貪心策略：優先確定身高維度，確保在插入過程中身高條件始終滿足。 數據結構選擇：選擇鏈表作為存儲隊列的數據結構，以提高插入操作的效率。
示例： 輸入：people = [[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]，隊列變為 [[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]] 輸出：[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
通過上述貪心策略和數據結構的選擇，我們可以高效地解決「leetcode」406.根據身高重建隊列的問題。