點(diǎn)贊👍👍收藏🌟🌟關(guān)注💖💖
你的支持是對(duì)我最大的鼓勵(lì)，我們一起努力吧!😃😃

1.最后一塊石頭的重量

題目鏈接：1046. 最后一塊石頭的重量

題目分析：

每一回合，從中選出兩塊 最重的 石頭，x == y，那么兩塊石頭都會(huì)被完全粉碎；如果 x != y，那么重量較小的 x 石頭將會(huì)完全粉碎，而重量較大的 y 的石頭新重量為 y-x。最多只會(huì)剩下一塊石頭。返回此石頭的重量。如果沒(méi)有石頭剩下，就返回 0。

算法原理：

每次挑選的是先挑一堆數(shù)中最大的那個(gè)數(shù)，然后再挑一個(gè)剩下數(shù)中最大的數(shù)。這不正好符合大根堆的數(shù)據(jù)結(jié)構(gòu)嗎。

解法：用堆來(lái)模擬這個(gè)過(guò)程

先拿數(shù)組的數(shù)創(chuàng)建一個(gè)大根堆，每次從堆里面選擇最大和次大兩個(gè)數(shù)，如果相等就是0不用加入到大根堆里，如果不相等用最大的數(shù)減去次大的數(shù)，把結(jié)果加入到堆里面。如果最后堆里還剩下一個(gè)數(shù)，返回這個(gè)數(shù)。如果堆為空說(shuō)明石頭全都粉碎了返回0即可。

class Solution {
public:int lastStoneWeight(vector<int>& stones) {//1.拿元素創(chuàng)建一個(gè)大根堆priority_queue<int> heap(stones.begin(),stones.end());//2.模擬這個(gè)過(guò)程while(heap.size() >= 2){int s1 = heap.top();heap.pop();int s2 = heap.top();heap.pop();if(s1 != s2) heap.push(s1 - s2);}return heap.size() ? heap.top() : 0;}
};

2.數(shù)據(jù)流中的第 K 大元素

題目鏈接：703. 數(shù)據(jù)流中的第 K 大元素

題目分析：

設(shè)計(jì)一個(gè)找到數(shù)據(jù)流中第 k 大元素的類（class）。注意是排序后的第 k 大元素，不是第 k 個(gè)不同的元素。

int add(int val) 將 val 插入數(shù)據(jù)流 nums 后，返回當(dāng)前數(shù)據(jù)流中第 k 大的元素。

算法原理：

這道題其實(shí)考察的是一個(gè)非常經(jīng)典的問(wèn)題， TopK問(wèn)題。
關(guān)于TopK問(wèn)題有兩種解題思路，一種是堆，一種是前面剛學(xué)的快速選擇算法。快速選擇排序雖然快，但是對(duì)于海量的數(shù)據(jù)內(nèi)存根本放不下。所以在海量數(shù)據(jù)情況最優(yōu)的還是堆。

解法：用 堆 來(lái)解決

1. 創(chuàng)建一個(gè)大小為 k 的堆（大根堆 or 小根堆）
2. 循環(huán)
   1.依次進(jìn)堆
   2.判斷堆的大小是否超過(guò) K

在堆的實(shí)現(xiàn)，畫(huà)圖和代碼分析建堆，堆排序，時(shí)間復(fù)雜度以及TOP-K問(wèn)題，對(duì)于求第K個(gè)最大元素，我們也是將前K個(gè)數(shù)建個(gè)小堆，然后將剩下的N-K個(gè)元素和堆頂元素做比較，如果大于堆頂元素，就先把棧頂元素pop掉，也就是把堆中最小元素刪除，然后將它放進(jìn)去。這樣一直循環(huán)，直到所有元素都比較完成。因?yàn)槭且恢卑讯阎凶钚〉膒op掉，那堆的元素就是N個(gè)元素中最大的，而堆頂就是第K個(gè)最大的元素，別忘記我們這是一個(gè)小堆！

這里我們也是建小堆，依次進(jìn)堆，當(dāng)堆大小超過(guò)K個(gè)，pop堆頂元素，把堆中最小元素pop掉，并且使堆保持K個(gè)大小。每次都是堆中最小元素去掉。那最后堆中剩下的就是前K個(gè)最大元素，而堆頂就是第K個(gè)最大元素。

考慮一下下面兩個(gè)問(wèn)題

1. 用大根堆還是小根堆
2. 為什么要用大根堆（小根堆）

class KthLargest {
public:priority_queue<int,vector<int>,greater<int>> heap;int _k;KthLargest(int k, vector<int>& nums) {_k = k;for(auto& x : nums){heap.push(x);if(heap.size() > k) heap.pop();}}int add(int val) {heap.push(val);if(heap.size() > _k) heap.pop();return heap.top();}
};

4.前K個(gè)高頻單詞

題目鏈接：692. 前K個(gè)高頻單詞

題目分析：

這是一個(gè)TopK的問(wèn)題，注意，返回的答案應(yīng)該按單詞出現(xiàn)頻率由高到低排序。如果不同的單詞有相同出現(xiàn)頻率， 按字典順序(由低向高) 排序。

算法原理：

解法：利用 “堆” 來(lái)解決 TopK 問(wèn)題

1. 預(yù)處理一下原始的字符串?dāng)?shù)組： 用一個(gè)哈希表，統(tǒng)計(jì)一下每一個(gè)單詞出現(xiàn)的頻次。

2. 創(chuàng)建一個(gè)大小為 k 的堆，類提供的比較函數(shù)滿足不了要求，我們要自己定義一個(gè)！（返回的答案應(yīng)該按單詞出現(xiàn)頻率由高到低排序。如果不同的單詞有相同出現(xiàn)頻率， 按字典順序(由低向高) 排序。）如果比較頻次創(chuàng)建一個(gè)小根堆，如果比較字典序(頻次相同的時(shí)候)創(chuàng)建一個(gè)大根堆。所以說(shuō)創(chuàng)建堆寫(xiě)比較函數(shù)的時(shí)候必須要考慮這兩點(diǎn)，當(dāng)頻次相同的時(shí)候字典序按照大根堆方式比較，當(dāng)頻次不同的時(shí)候按照小根堆方式比較。

3. 循環(huán)
   1.依次進(jìn)堆
   2.判斷堆的大小是否超過(guò) K

4. 提取結(jié)果

因?yàn)榍笄癒大，所以建的是一個(gè)小根堆，然后提取堆頂元素在pop是一個(gè)升序的。有兩種方式拿最終答案，要么逆序一下取前K個(gè)，要么從后往前取K個(gè)。

class Solution {
public:struct Compare{bool operator()(const pair<string,int>& l,const pair<string,int>& r){//頻次不同按照小根堆比較, 頻次相同字典序按照大根堆方式比較return l.second > r.second || (l.second == r.second && l.first < r.first);}};vector<string> topKFrequent(vector<string>& words, int k) {vector<string> ret;// 1.統(tǒng)計(jì)一下每一個(gè)單詞的頻次map<string,int> count;for(auto& str : words){count[str]++;}// 2.創(chuàng)建一個(gè)大小為 k 的小堆priority_queue<pair<string,int>,vector<pair<string,int>>,Compare> heap;// 3.TopK 的主邏輯for(auto& m : count){heap.push(m);if(heap.size() > k) heap.pop();}// 4.提取結(jié)果vector<string> tmp;while(!heap.empty()){tmp.push_back(heap.top().first);heap.pop();}reverse(tmp.begin(),tmp.end());for(int i = 0; i < k; ++i)ret.push_back(tmp[i]);return ret;}
};

4.數(shù)據(jù)流的中位數(shù)

題目鏈接：295. 數(shù)據(jù)流的中位數(shù)

題目分析：

給一個(gè)數(shù)據(jù)流，讓返回每次當(dāng)前已經(jīng)加入到數(shù)組的數(shù)據(jù)流的中位數(shù)。中位數(shù)是有序整數(shù)列表中的中間值。如果列表的大小是偶數(shù)，則沒(méi)有中間值，中位數(shù)是兩個(gè)中間值的平均值。表的大小是奇數(shù)，直接返回中間的數(shù)。

算法原理：

解法一：直接sort

每次從數(shù)據(jù)流中來(lái)一個(gè)數(shù)插入數(shù)組中之后，都對(duì)當(dāng)前數(shù)組進(jìn)行sort，然后通過(guò)下標(biāo)的方式找到中間數(shù)。

每次add加入一個(gè)數(shù)都要sort，時(shí)間復(fù)雜度是O(nlogn)。總體時(shí)間復(fù)雜度是非?？植赖?。因?yàn)槭窍聵?biāo)訪問(wèn)，find 時(shí)間復(fù)雜度是 O(1)

解法二：插入排序的思想

[0,end] 有序，插入 end + 1，使 [0, end + 1]有序。這道題正好就是這樣的思想。

add函數(shù)，每次插入一個(gè)數(shù)的時(shí)候都需要從后往前掃描找一個(gè)插入的位置，因此時(shí)間復(fù)雜度是O(n)，find 也是通過(guò)下標(biāo)去找 時(shí)間復(fù)雜度是O(1)

解法三：大小堆來(lái)維護(hù)數(shù)據(jù)流的中位數(shù)

此時(shí)有一個(gè)數(shù)軸已經(jīng)按照從小到大的排好序了，這個(gè)時(shí)候想找中間數(shù)的時(shí)候。把這些數(shù)的前半部分放到一個(gè)大根堆里面，后半部分放到小根堆里面。此時(shí)找中間值也很快，前面較小的數(shù)放到大根堆里面，堆頂元素是數(shù)軸中這些較小元素種最右邊的值。后面較大的數(shù)放到小根堆里面，堆頂元素是數(shù)軸中這些較大元素最左邊。此時(shí)我們僅需根據(jù)數(shù)組中的元素的個(gè)數(shù)就可以求出中位數(shù)是多少了。如果數(shù)組是偶數(shù)個(gè)大根堆和小根堆正好把數(shù)軸平分，然后大堆堆頂元素和小堆堆頂元素相加/2就是這個(gè)數(shù)組的中位數(shù)。如果數(shù)組是奇數(shù)個(gè)。我們就先人為規(guī)定一下，數(shù)軸左邊元素是m個(gè)，右邊是n個(gè)，要么 m == n，要么 m > n （n = n + 1）。如果 m == n 正好平均分。如果數(shù)軸個(gè)數(shù)是奇數(shù)個(gè)，人為規(guī)定左邊大根堆多方一個(gè)元素，m > n(n = n + 1)，此時(shí)中位數(shù)就是左邊大根堆的堆頂元素。

向這樣用大根堆存左邊較小部分，小根堆存右邊較大部分。find 時(shí)間復(fù)雜度也是O(1)，而add快了很多，因?yàn)槲覀兪菑亩汛孢@些元素的，插入和刪除每次調(diào)整堆僅需O(logn)

細(xì)節(jié)問(wèn)題：

add如何實(shí)現(xiàn)：
假設(shè)現(xiàn)在有兩個(gè)堆了。一個(gè)大根堆left，一個(gè)小根堆right。left元素個(gè)數(shù)m個(gè)，right元素個(gè)數(shù)n個(gè)，left堆頂元素x，right堆定元素y。如果此時(shí)來(lái)了一個(gè)數(shù)num，num要么放在left里，要么放在right里。但是放好之后可能會(huì)破壞之前的規(guī)則：

1. m == n
2. m > n —> m == n + 1

我們必須維護(hù)上面的規(guī)則，才能正確找到數(shù)組中位數(shù)。
接下來(lái)分情況討論：

1. m == n

num要么插入left，要么插入right。

如果num要進(jìn)入left，那么num <= x，但是別忘記 m == n 有可能兩個(gè)堆全為空，num也是直接進(jìn)入left。此時(shí) m 比 n 多了一個(gè)。沒(méi)關(guān)系直接進(jìn)就行。

如果num進(jìn)入right，那條件是 num > x。此時(shí)就有問(wèn)題了。n > m了，而 n > m是不被允許的，所以我們要把右邊堆調(diào)整一下，就是拿right堆頂元素放到left里。因?yàn)閞ight是一個(gè)小根堆，堆頂就是最小值。拿到left，還是能保證left堆里元素是較小的，right堆里元素是較大的。拿right堆頂元素放到left里正好滿足 m == n + 1。這里有一個(gè)細(xì)節(jié)問(wèn)題，必須num先進(jìn)right堆，然后再拿right堆定元素放到left，因?yàn)?x < num < y，如果直接把y拿過(guò)去了，就破壞了left都是較小元素。right都是較大元素。

2. m > n —> m == n + 1

如果num進(jìn)入left，那么num <= x ， 但是此時(shí)不滿足 m == n + 1，因此 進(jìn)棧后將棧頂元素給right。

如果num進(jìn)入right，那么num > x , m == n了，直接進(jìn)就行了

class MedianFinder {
public:MedianFinder() {}void addNum(int num) {// 分類討論即可int m = left.size(), n = right.size();if(m == n) // 左右兩個(gè)堆的元素個(gè)數(shù)相同{if(m == 0 || num <= left.top())left.push(num);else{right.push(num);left.push(right.top());right.pop();}}else //左邊堆的元素個(gè)數(shù)比右邊堆元素個(gè)數(shù)多 1{if(num <= left.top()){left.push(num);right.push(left.top());left.pop();}elseright.push(num);}}double findMedian() {int m = left.size(), n = right.size();if(m == n) return (left.top() + right.top()) / 2.0;else return left.top();}private: priority_queue<int> left;priority_queue<int,vector<int>,greater<int>> right;
};