算法打卡 Day13（栈与队列）-滑动窗口最大值 + 前 K 个高频元素 + 总结

文章目录

• Leetcode 239-滑动窗口最大值
• • 题目描述
  • 解题思路
  • Leetcode 347-前 K 个高频元素
  • • 题目描述
    • 解题思路
    • 栈与队列总结

      Leetcode 239-滑动窗口最大值

      题目描述

      https://leetcode.cn/problems/sliding-window-maximum/description/

      解题思路

      在本题中我们使用自定义的单调队列来实现：

      pop：如果窗口移除的元素 value 等于单调队列的出口元素，那么队列弹出元素，否则不进行任何操作

      push：如果 push 的元素 value 大于入口元素的数值，那么就将队列入口的元素弹出，直到 push 元素的数值小于队列入口元素的数值为止

      返回当前窗口的最大值：调用 que.front()

      class Solution {private:
          class MyQueue { public:
              deque que; //使用deque实现单调队列
              void pop(int value) { if (!que.empty() && value == que.front()) { que.pop_front();
                  }
              }
              void push(int value) { while (!que.empty() && value > que.back()) { que.pop_back();
                  }
                  que.push_back(value);
              }
              int front() { 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.front());
              for (int i = k; i < nums.size(); i++) { que.pop(nums[i - k]);
                  que.push(nums[i]);
                  result.push_back(que.front());
              }
              return result;
          }
      };
      

      Leetcode 347-前 K 个高频元素

      题目描述

      https://leetcode.cn/problems/top-k-frequent-elements/description/

      解题思路

      这道题目需要解决三个部分的问题：

      1. 统计元素的出现频率：

      我们可以使用 unordered_map 来解决，其中 key 表示元素的值，value 表示值出现的次数

      2. 对频率进行排序：

      使用优先级队列，其是一个披着队列外衣的堆。优先级队列对外接口是从队头取元素，从队尾添加元素，其内部的元素自动依照元素的权值排列。优先级队列缺省情况下 priority_queue 利用 max-heap 大顶堆完成对元素的排列，大顶堆是以 vector 为表现形式的完全二叉树。

      堆是完全二叉树，树中的每个结点都不小于（或不大于）其左右孩子的值。父亲结点大于等于左右孩子的是大顶堆，小于等于左右孩子的是小顶堆。

      选用优先级队列而不是快排：我们只需要报告前 K 个高频元素而不是全部元素，因此只需要维护 K 个有序序列即可，当 n 非常大时，这样的方法可以降低时间复杂度。

      使用小顶堆而不是大顶堆：因为要统计最大前 K 个元素，如果选用大顶堆会将最大的元素弹出不符合要求，而使用小顶堆可以每次将最小的元素弹出，最后小顶堆中积累的才是前 K 个最大元素。

      3. 找出前 K 个高频元素

      class Solution {public:
              //小顶堆
              class mycomparison{ public:
                      bool operator()(const pair& lhs, const pair& rhs) { return lhs.second > rhs.second;
                      }
              };
          vector topKFrequent(vector& nums, int k) { //统计元素出现的频率
                      unordered_mapmap;
                      for (int i = 0; i < nums.size(); i++) { map[nums[i]]++;
                      }
                      //根据频率进行排序
                      //定义一个小顶堆，大小为k
                      priority_queue, vector>, mycomparison> pri_que;
                      //用固定大小为k的小顶堆，扫描所有频率的数值
                      for (unordered_map::iterator it = map.begin(); it != map.end(); it++) { pri_que.push(*it);
                              if (pri_que.size() > k) {//如果堆的大小大于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;
          }
              
      };
      

      栈与队列总结

      栈和队列是容器适配器，底层容器使用不同的容器，那么栈内数据在内存中的分布就不一定连续。

      在缺省状况下，栈和队列的默认底层容器时 deque，其内存分布不连续。

      递归的实现是栈：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。