Day13 LeetCode 239、347

今日内容： 

•  239. 滑动窗口最大值
  •  347.前 K 个高频元素
    •  总结

       239. 滑动窗口最大值 （一刷至少需要理解思路）

      队列的应用

      使用双端队列，构建单调递减队列，队首元素为最大值，自定义数据结构

      class Solution {
      private:
          class Myqueue{
          public:
              deque que;//双端队列
              void pop(int val){
                 if(!que.empty() && val == que.front()){
                     que.pop_front();
                  }
              }
              void push(int val){
                  while(!que.empty() && val > que.back()){
                      que.pop_back();         
                  }
                  que.push_back(val);
              }
              int getMax(){
                  return que.front();
              }
          };
      public:
          
          vector maxSlidingWindow(vector& nums, int k) {
              Myqueue que;
              vector  result;
              for(int i = 0; i < k; i++){
                  que.push(nums[i]);
              }
              result.push_back(que.getMax());
              for(int i = k; i < nums.size(); i++){
                  que.pop(nums[i-k]);
                  que.push(nums[i]);
                  result.push_back(que.getMax());
              }
          return result;
          }
      };

       

      题目链接/文章讲解/视频讲解：代码随想录

       347.前 K 个高频元素  （一刷至少需要理解思路）

      大/小顶堆的应用， 在C++中就是优先级队列 ,在优先级队列中保存map数组，以value值作为排序比较数值。

      class Solution {
      public:
          //重写比较逻辑
          class greater{
          public:
              bool operator()(const pair& key1,const pair& key2){
                  return key1.second > key2.second;
              }
          };
          vector topKFrequent(vector& nums, int k) {
              //统计元素出现频率
              unordered_map map;//键值对形式 key:nums[i] value:出现频率
              for(int i = 0; i < nums.size(); i++){
                  map[nums[i]]++;
              }
              //对value值排序，小顶堆找前k个元素
              priority_queue,vector>,greater> pri_que;
              //将所有map键值对按value值进行小根堆（大小为k）排序
              for(unordered_map::iterator it = map.begin(); it != map.end(); it++){
                  pri_que.push(*it);
                  if(pri_que.size() > k){
                      pri_que.pop();
                  }
              }
              //保存频率前k高的元素
              vector result(k);
              for(int i = k - 1; i >= 0; i--){
                  result[i] = pri_que.top().first;
                  pri_que.pop();
              }
              return result;
          }
      };

      题目链接/文章讲解/视频讲解：代码随想录

       总结 

      栈与队列

      代码随想录