引言239. 滑动窗口最大值 - 力扣LeetCode347. 前 K 个高频元素 - 力扣LeetCode第一题这一题我们将引入一个单调队列可能大家对于单调栈并不陌生但是单调队列的题目可能接触的比较少。单调队列解决的问题就是维护一个窗口的数据类似于大顶堆的作用但是并不是大顶堆。比如说大顶堆优先队列对于13-1来说就变成了31-1但是我们可以发现当我们窗口移动的时候我们需要把1弹出去但是无论我们是从头还是尾都无法弹出1所以我们需要自己构造一个单调队列。我们这个队列里面只需要维护最大的元素还是13-1当我们3进入之后1就会自动的被我们弹出去因为我们要求的是最大的元素既然已经有3进来了那么1的存在已经没有任何的意义了所以只要有比前面大的元素进来那么就会自动把前面那些比这个元素小的元素卷走不需要我们在主函数里面手动调用pop函数。这样子我们就可以永远保证队头的元素是最大值并且从队头到队尾元素的大小依次减小。所以每次我们需要知道这个队列里面最大值是多少的时候就访问队头元素即可。我们这个队列是双端队列也就是用deque实现的而我们的队头是出队列的队尾是入队列的pop的含义就是每一次移动窗口的时候把多余的那一个元素从队头弹出去注意这个操作并不包含我们加入一个比之前的大的元素然后把前面那些元素弹走原理就是我们只需要维护这个队列里面最大的元素一定要把最大的元素放在队头push函数就是加入元素不过在加入元素之前要比较末尾的元素为什么是末尾的元素呢因为我们的队列是递减的比如53要加入4那么如果比较队头就无法把3出队而比较队尾就是把3出队然后把4入队变成54最后在主函数里面我们先把队列里面的元素全部初始化好然后窗口开始往后面移动至于我们为什么要值传递是因为方便我们直接操作元素用nums[i-k]class MyQueue { public: dequeint 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 getMaxValue () { return que.front(); } }; class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { MyQueue que; vectorint res; for (int i 0; i k; i) { que.push(nums[i]); } res.push_back(que.getMaxValue()); for (int i k; i nums.size(); i) { que.pop(nums[i - k]); que.push(nums[i]); res.push_back(que.getMaxValue()); } return res; } };第二题这一题用的是优先队列来解决前k个元素的问题优先队列的底层是大顶堆和小顶堆来实现的也就是我们在使用优先队列的时候是需要传入我们使用的是那个堆的cmp函数。这一题主要的难点就是我们到底是使用大顶堆还是小顶堆大顶堆的根节点是最大值我们每一次插入结点都会把堆顶的元素弹出去然后把新加入的元素放入堆顶然后从根节点开始重新调整这个堆小顶堆也是一样。所以如果我们使用的是大顶堆我们每一次弹出去的是最大频率的那一个最后维护了k个最小的频率元素。所以我们应该使用小顶堆class Solution { public: class cmp { public: bool operator()(const pairint, int a, const pairint, int b) { return a.second b.second; } }; vectorint topKFrequent(vectorint nums, int k) { unordered_mapint, int umap; for(int i 0; i nums.size(); i) { umap[nums[i]]; } priority_queuepairint, int, vectorpairint, int, cmp que; for(auto iter umap.begin(); iter ! umap.end(); iter) { que.push(*iter); if (que.size() k) { que.pop(); } } vectorint res(k, 0); for (int i k - 1; i 0; i--) { res[i] que.top().first; que.pop(); } return res; } };对于堆的调整代码我这里也给出来了这里传递的i就是1因为是堆顶然后不断的向下调整void DownAdjust(int a[], int i, int n) { // 向下调整 int now i; // 当前结点 int next; // 值最大的孩子 while(2 * now n) { // now的左子树存在,也就是说当前结点至少有一个孩子 next 2 * now; if(2 * now 1 n a[2 * now 1] a[next]) { // 右子树存在且右孩子值更大 next 2 * now 1; } if(a[now] a[next]) { // 父亲比孩子小 std::swap(a[now], a[next]); now next; // 再继续向下调整 }else { // 如果父亲比孩子大说明已经是大顶堆了不需要调整了 break; } } }