一、最后一塊石頭的重量

. - 力扣（LeetCode）

? ? ? ? 我們每次都要快速找到前兩個最大的石頭進行抵消，這個時候用優先級隊列（建大堆）,不斷取堆頂元素是最好的！每次刪除堆頂元素后，可以自動調整，時間復雜度是logN。

class Solution {
public:int lastStoneWeight(vector<int>& stones) {//建立優先級隊列  大堆priority_queue<int> heap;for(auto&num:stones) heap.push(num);while(heap.size()>1){int x=heap.top();heap.pop();int y=heap.top();heap.pop();if(x>y) heap.push(x-y); }return heap.size()?heap.top():0;//不為空，就返回堆頂元素，為空，就返回0}
};

二、數據流中的第K大元素

. - 力扣（LeetCode）

（1）在學習分治專題的時候，我們知道topK問題可以用優先級隊列去解決也可以用快速排序的三路劃分去解決，并且快速排序反而會更優秀一點，那優先級隊列的優勢究竟體現在哪里呢？？其優勢體現在可以不斷地去取用堆頂元素或者是加入元素的時候都可以通過用logN的時間復雜度進行調整，而前期建堆也僅僅是N*logN的時間復雜度，而快速排序的三路劃分則是一次性的N的時間復雜度，所以長期優先級隊列收益高，短期收益快速排序的三路劃分收益高。

class KthLargest {priority_queue<int,vector<int>,greater<int>> heap;//仿函數int k;   //創建一個大小為k的小根堆 堆頂始終是第k大的元素//用快速排序算法可以是O（N）的復雜度，但是如果是要頻繁去獲取，就很顯然得依靠優先級隊列
public:KthLargest(int _k, vector<int>& nums) {k=_k; for(auto &val:nums) {heap.push(val);if(heap.size()>k) heap.pop();//入堆的同時進行向上調整}}int add(int val) {heap.push(val);if(heap.size()>k)heap.pop();//可能我插入的時候堆里啥也沒有return heap.top();}
};

?三、數據的中位數

. - 力扣（LeetCode）

策略1：存在數組中用sort去排序? ——?add（NlogN）? find(1)?

策略2：還是存在數組中，利用插入排序的思想，因為插入之間就已經是有序的了，所以新元素插入時的時間復雜度是插入排序的最好情況O（N）? ?——add(N)? ?find(1)

策略3：優先級隊列大小堆維護中位數? ?add(logN)? find(1)

設計思路：

1、建立left為大根堆，right為小根堆

2、我們的add控制始終保持left的數量要么和right相等，要么比right多一個，為了能夠滿足在O（1）的復雜度內完成找到中位數的任務，我們希望當left多一個的時候，left堆頂的元素就是中位數，而當left和right相等的時候，中位數就是兩個堆的堆頂元素的平均值。

3、為了達到這個目的，我們在時刻控制left和right的數量的同時，一定要保證left里面的元素是小于等于right里面的元素的，所以add要分兩種情況去討論：

情況1：當兩個堆的元素個數相等的時候

? ? （1）如果left為空，或者是add的元素比left的堆頂元素小，那么就讓該元素直接進left

? ? （2）如果add的元素比left的堆頂元素大，那么他也有可能會比right的元素大，所以我們必須要將這個元素丟到right中，但是直接丟就會破壞規則，所以我們要先將add的元素丟到right中進行調整，然后再將right的堆頂元素丟到left中去，保持left和right的數量關系。 （注意，這里的先后順序很重要，我們不能先將right的堆頂元素丟到left中，然后再將add丟到right中進行調整，因為我們只是知道這個數比left的堆頂元素大，但是他是比right的堆頂元素大還是小我們不得而知，必須要通過他自己的向下調整去選出來）

情況2：當left的元素比right多一個的時候

? （1）如果add的元素比left的堆頂元素大，這個時候無腦進右邊就行了。

? ?（2）如果add的元素比left的堆頂元素小，這個時候我們也得把add的元素丟到left中，然后為了保持數量關系，將調整過后的left的堆頂元素移到right中即可。

細節處理：

1、我們在比較的時候始終實用left的元素進行比較，因為左邊不為空的時候右邊也可能為空，所以我們如果不用left去比較而是用right去比較，那么還需要多考慮一種邊界情況。

2、雖然我們add的都是int類型，但是當兩個堆的元素個數相同的時候，我們去取兩個堆頂元素取平均值的，而平均值是有可能會出現小數的，所以如果我們還用int的話可能會造成小數點丟失，所以我們在/2的時候變成/2.0,這樣結果就會被強轉成double；

class MedianFinder {
public:MedianFinder() {} //默認初始化不管了void addNum(int num) {//分類討論 m==n或者m==n+1size_t m=left.size(),n=right.size();if(m==n) //m==n->m==n+1{//如果我比左邊的堆頂小，或者是為空，我就進左邊if(m==0||num<=left.top()) left.push(num);else //如果我比堆頂大,那我要進右邊，然后把右邊的移過來{right.push(num);left.push(right.top());right.pop();}}else // m==n+1 ->m==n{//如果我比左邊的小，直接進右邊即可if(num <= left.top()) {left.push(num);right.push(left.top());left.pop(); }else //如果我比左邊的大 無腦進右邊 right.push(num);}}double findMedian() { //我們的策略是 m==n 返回堆頂平均值  如果m==n+1 返回左邊的堆頂if(left.size()>right.size()) return left.top();else return (left.top()+right.top())/2.0;}private:priority_queue<int> left;//左邊是大根堆priority_queue<int,vector<int>,greater<int>> right;///右邊是小根堆
};

四、?前K個高頻詞匯

. - 力扣（LeetCode）

該題是一道非常經典的OJ題，在哈希表章節中介紹了四種解法，運用stl中的不同容器去解決。

算法思想總結：哈希表-CSDN博客

class Solution {
public:typedef pair<string,int> PSI;struct compare//要注意仿函數要+const修飾，否則可能編譯不過{bool operator()(const PSI&kv1,const PSI&kv2) const{if(kv1.second==kv2.second) return kv1.first<kv2.first;return kv1.second>kv2.second;}};vector<string> topKFrequent(vector<string>& words, int k) {unordered_map<string,int> countmap;//計數for(auto&s:words) ++countmap[s];//丟到優先級隊列里priority_queue<PSI,vector<PSI>,compare> heap;for (auto& it : countmap) {heap.push(it);if (heap.size() > k) heap.pop();}vector<string> ret(k);for(int i=k-1;i>=0;--i) {ret[i]=heap.top().first;heap.pop();}return ret;}
};