摘要

• 如何用雙端隊(duì)列deque實(shí)現(xiàn)單調(diào)隊(duì)列，單調(diào)隊(duì)列是指，隊(duì)列中的元素順序按非遞增、非遞減、遞增、遞減中的一種的隊(duì)列。
  • 隊(duì)首根據(jù)窗口的滑動(dòng)出隊(duì)
  • 隊(duì)尾根據(jù)元素的大小出隊(duì)
• 優(yōu)先級(jí)隊(duì)列priority_queue，大頂堆、小頂堆的使用

今日學(xué)習(xí)的視頻和文章

• 代碼隨想錄 滑動(dòng)窗口最大值
• 代碼隨想錄 前k個(gè)高頻元素
• C++Primer 雙端隊(duì)列部分
• 數(shù)據(jù)結(jié)構(gòu)C++語言版第二版（清華大學(xué)出版社）大頂堆、小頂堆的實(shí)現(xiàn)
• C++函數(shù)指針

LeetCode239 滑動(dòng)窗口最大值

239. 滑動(dòng)窗口最大值 - 力扣（Leetcode）

• 初見題目的想法：

  • 這道題目中，滑動(dòng)窗口中可能的最大值有兩種排除可能方式：

    1. 滑動(dòng)窗口滑過了某個(gè)可能的最大值，即該可能最大值不再被包含在當(dāng)前的滑動(dòng)窗口內(nèi)。如以下例子，3不在窗口內(nèi)。

    1 3 [1 2 0] 5
    

    2. 有一個(gè)新的可能最大值進(jìn)入滑動(dòng)窗口，其他比這個(gè)可能最大值小且有可能在同一個(gè)滑動(dòng)窗口內(nèi)的值都不可能成為滑動(dòng)窗口的最大值?？梢?，在如下的滑動(dòng)過程中，3和2之間的1，不會(huì)有成為滑動(dòng)窗口最大值的可能。

    1 [3 1 2] 0 5
    1 3 [1 2 0] 5
    

• 而滑動(dòng)窗口中的元素先進(jìn)先出，這讓人很自然的聯(lián)想到隊(duì)列，所以上述的兩個(gè)排除可能最大值的方式對(duì)應(yīng)到元素的出隊(duì)方式就是：

  1. 隊(duì)首的元素根據(jù)窗口的滑動(dòng)出隊(duì)，如果隊(duì)首的元素已經(jīng)不在當(dāng)前滑動(dòng)窗口內(nèi)，則出隊(duì)
  2. 隊(duì)尾的元素根據(jù)滑動(dòng)窗口包含的新的值出隊(duì)，如果隊(duì)尾的元素比滑動(dòng)窗口包含進(jìn)的新的一個(gè)值小，則隊(duì)尾的元素出隊(duì)

• 由于需要從隊(duì)首和隊(duì)尾兩個(gè)方向?qū)⒃爻鲫?duì)，所以考慮使用雙端隊(duì)列deque

完整的題解代碼如下，此處的題解代碼的單調(diào)隊(duì)列保存的是元素的下標(biāo)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> q;
        for (int i = 0; i < nums.size(); i++) {
            if (!q.empty() &&  i - q.front() == k) {
                q.pop_front();
            }
            while (!q.empty() && nums[i] > nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
            if (i + 1 >= k) {
                res.push_back(nums[q.front()]);
            }
        }
        return res;
    }
};

• 看了講解之后的思考：
  • 維護(hù)單調(diào)隊(duì)列的關(guān)鍵：嘗試新入隊(duì)的元素不斷與隊(duì)尾元素比較，若隊(duì)尾元素和嘗試新入隊(duì)的元素不符合我們定義的順序，則讓隊(duì)尾元素出隊(duì)。而隊(duì)首元素的出隊(duì)是由于滑動(dòng)窗口的滑動(dòng)導(dǎo)致包含的元素的變化。

LeetCode 347前k個(gè)高頻元素

347. 前 K 個(gè)高頻元素 - 力扣（Leetcode）

• 解題思路：

  • 先遍歷一遍數(shù)組nums，使用哈希表unordered_map來記錄各元素的出現(xiàn)的頻率。
  • 由于題目只要求返回前k個(gè)高頻元素，所以可以考慮將頻數(shù)在后n-k個(gè)的元素排除。
  • 如果使用大頂堆，當(dāng)堆中元素個(gè)數(shù)到達(dá)k個(gè)時(shí)，由于后面還有至少n-k個(gè)元素沒有進(jìn)入堆中排序，所以也無法確定堆頂是否是在前k個(gè)高頻元素中。
  • 如果使用小頂堆，當(dāng)堆中元素到達(dá)k個(gè)時(shí)，再往堆中加入一個(gè)元素并調(diào)整為小頂堆后，由于堆頂是當(dāng)前k+1個(gè)元素內(nèi)頻數(shù)最小的元素，所以可以確定堆頂元素中不會(huì)在前k個(gè)高頻元素中。將堆頂元素彈出即可（因?yàn)橐呀?jīng)確定有k個(gè)元素的頻數(shù)大于堆頂元素的頻數(shù)，自然最后的答案不會(huì)有目前的堆頂元素）。

  使用大頂堆	使用小頂堆
  對(duì)所有元素按頻數(shù)進(jìn)行堆排序，然后從堆頂取k個(gè)元素，即為題目要求的k個(gè)高頻元素	在遍歷元素時(shí)，保持堆中的元素為k個(gè)，遍歷完成時(shí)，小頂堆中保留的元素即為題目要求的k個(gè)元素
  實(shí)際上是對(duì)所有元素按頻數(shù)進(jìn)行排序，然后取前k個(gè)高頻元素	實(shí)際上就是優(yōu)先隊(duì)列的思想，頻數(shù)高的保留在隊(duì)列中，頻數(shù)低的優(yōu)先出隊(duì)

  完整題解代碼如下

  class Solution {
  public:
  
      class minHeapCmp {
      public:
          bool operator()(const pair<int, int>& l, const pair<int, int>& r) {
              return l.second > r.second;
          }
      };
  
      vector<int> topKFrequent(vector<int>& nums, int k) {
          unordered_map<int, int> map;
          for (auto& iter : nums) {
              map[iter]++;
          }
  
          priority_queue<pair<int, int>, vector<pair<int, int>>, minHeapCmp> minHeap;
          for (auto& iter : map) {
              minHeap.push(iter);
              if (minHeap.size() > k) {
                  minHeap.pop();
              }
          }
  
          vector<int> ans(k);
          for (int i = k - 1; i >= 0; i--) {
              ans[i] = minHeap.top().first;
              minHeap.pop();
          }
          return ans;
      }
  };
  

• 疑惑及要注意的地方：

  • 優(yōu)先級(jí)隊(duì)列自定義的比較規(guī)則，為什么是l.second > r.second，我沒有深入的理解，等之后復(fù)習(xí)完樹的內(nèi)容后，我會(huì)嘗試用C++實(shí)現(xiàn)一個(gè)可以自定義比較規(guī)則的堆來幫助理解。
  • STL為編程提供了很多便利，但不僅要知道怎么用，更要在使用的過程中思考STL是如何實(shí)現(xiàn)的。排斥STL和過度依賴STL都是不利于學(xué)習(xí)的。