算法Day13

算法Day13"/>

算法Day13

Day13

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

239. 滑动窗口最大值

题目链接： 239. 滑动窗口最大值
构造一个单调队列deque，维护最大值：依次push每个元素。如果当前元素小于队尾元素，则直接push，如果大于队尾元素，则将队尾元素pop掉，再push该元素。根据此规则，一直维持队首元素为最大元素。
对于滑动窗口的第一个元素来说，下一次窗口的移动将移除该元素，如果该元素为当前队首元素（既为最大元素），将直接pop该元素，否则不用特别处理，因为在push时，可能已经处理掉该元素。
只要一直维持该单调性即可。

将完整的遍历根据窗口分出两次，完成滑动窗口使用。

class Solution {
private:class MyQue {public:deque<int> que;//构造单调队列void push(int& val) {while (!que.empty() && val > que.back()/*加入的依次比较，比val小的都弹出，用来维持单调性*/) {que.pop_back();}que.push_back(val);}void pop(int& val) {if (!que.empty() && val == que.front()/*如果弹出的值为队首（最大值），则弹出*/) {que.pop_front();}}//因为维护的是单调队列，直接获取队首即可int getNextValue() {return que.front();}};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> res;MyQue que;for (int i = 0; i < k; ++i) {//加入第一个窗口的值que.push(nums[i]);}res.push_back(que.getNextValue());for (int i = k; i < nums.size(); ++i) {//补上之前的遍历，使其完整遍历que.pop(nums[i - k/*维护窗口的大小*/]);que.push(nums[i/*维护窗口的大小*/]);res.push_back(que.getNextValue());}return res;}

347.前 K 个高频元素

题目链接：347.前 K 个高频元素
用map和排序，排序取前k个。其中，排序中快排时间复杂度为 O ( n × log ⁡ n ) O(n \times\log n) O(n×logn)

维护前K个高频元素的集合。可以用到的结构为大根堆和小根堆（堆结构擅长在数据集里求前k个高频或者低频的操作）。大根堆，根节点最大，小根堆，根节点最小。由于堆的弹出是对根节点弹出，所以要用小根堆。 堆的时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)，对前k个复杂度为 O ( log ⁡ k ) O(\log k) O(logk)。遍历一遍是时间复杂度为 O ( n ) O(n) O(n)，整体来说是 O ( n × log ⁡ k ) O(n\times\log k) O(n×logk)。

优先级队列priority_queue的底层实现就是堆，是大根堆还是小根堆需要自定义比较函数cmp。

class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> map;vector<int> res;for (int i = 0; i < nums.size(); ++i) {map[nums[i]]++;//key 数字，value出现的次数}auto cmp = [](const auto& lhs, const auto& rhs) {return lhs.second > rhs.second;};//比较函数priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> que(cmp);//小根堆for (auto it = map.begin(); it != map.end(); ++it) {//遍历mapque.push(*it);//加入小根堆if (que.size() > k) {//保留前k个que.pop();}}while (!que.empty()) {res.push_back(que.top().first);que.pop();}return res;}
};

堆

堆是一种特殊的二叉树结构，它具有以下两个特点：

完全二叉树性质：完全二叉树是指除了最后一层外，其他所有层的节点都必须填满，并且最后一层的节点都靠左排列。这意味着在一个完全二叉树中，除了最后一层外，其他层的节点数量都是满的，最后一层的节点数量可能不满。

堆特性：堆满足堆特性，即对于任意节点i，其父节点的值大于（或小于）其子节点的值。如果父节点的值大于子节点的值，则称为大根堆；如果父节点的值小于子节点的值，则称为小根堆。

由于在堆中的任意一棵子树都满足堆的特性，则可以通过数组来表示堆。具体表示方法为：将堆中的元素按照完全二叉树的性质，从左到右、从上到下依次存储在数组中。假设堆中的元素按照从1开始编号，那么对于某个节点i，它的左子节点为2i，右子节点为2i+1，父节点为i/2（向下取整）。这样的数组表示方式在实现中更加高效，因为不需要额外的指针来表示节点之间的连接关系。