代码随想录 | Day14 | 栈和队列：滑动窗口最大值&&前K个高频元素

主要学习内容：

1.使用单调队列解决滑动窗口

2.使用优先级队列

3.map的第二个元素的排序问题

239.滑动窗口最大值

239. 滑动窗口最大值 - 力扣（LeetCode）

思路：

使用单调队列维护一个单调递减的队列，具体看这个例子

举例子来说明：

nums={2,1,4,2,3,2},k=3

image-20240602142731714

假设你在坐飞机，你的面前是要飞越的山，数组就是它们的高度，你的视野范围即你能看到的山的数量是滑动窗口大小，题目要求是，你想要找到视野范围内最高的山并且记录下来

单调队列的模拟过程

  1. 首先是 2 1进入你的眼帘，我们把2 1入队

  2. 当4进入你的视野后，2和1就再也不可能是你视野中最高的山了

所以我们在 2 1 4中删去 2 1留下4，现在队中只剩下4，所以你在第一块视野内最高的山峰是4，记录下来

  1. 接着飞机飞到了2

2有可能成为你视野中的最大值，因为4可能会离开你的视野，即滑动窗口内已经不包含4了，所以入队

此时4仍然是视野内最高的山峰，记录下来

  1. 接着飞到了 3

再遇到3时就和2 1 遇到4一样，这里的2也不可能成为你视野中的最高的山峰了

所以删除2 此时队列剩下的是 4 3，4仍然是你视野中最高的山峰，记录下来

  1. 接着飞到了 2

2比3小，有可能成为你视野中最高的山峰，入队

注意，当飞机飞到了2，你的视野中就不包含4了，因为你的视野只能有3座山 此时是2 3 2，第一个2已经在第4步被删掉了

4不在视野内当然要删掉了，所以队列内只剩下3 2

最高的山峰就是3，记录下来，遍历到了数组末尾，遍历结束

模拟结束我们可以回答这样的问题

为什么要用单调队列？

因为要让队首元素成为我们要的最大值，它前面的比它小的在我们的队列中没有必要维护，因为它们不可能成为视野内最高的山峰就像4前面的 2 1一样

就像是4 2 3一样，没有遇到3时，2还有可能是最大值，遇到3之后2再也不可能成为最大值，所以要删去2留下 4 3保持队列单调递减，这样就只留下了最大值和接下来有可能成为最大值的山峰

代码实现

接下来的任务就是代码实现我们的模拟过程，最好用单调队列记录对应元素的下标而不是这个元素，具体原因可以看下面

分为4步

1.删除元素，让队列保持单调递减

1
2
3
4
5
6
7
8
9
//如果队列不为空并且当前的山峰高于队列末尾的山峰 就一直弹出，直到队列末尾元素大于等于当前山峰，保持了队列单调递减

//2 1 4 (此时4还没有进入队列)
//4>1 弹出1 4大于2 弹出2

//4 2 3
//3>2 弹出2 3<4 结束删除元素的过程
while(!q.empty()&&nums[i]>nums[q.back()])
                q.pop_back();

2.元素入队

1
q.push_back(i);

3.检查队首元素是否已经滑出窗口

1
2
3
//当前元素和队首元素下标之间距离大于滑动窗口大小
if(i-q[0]+1>k)
                q.pop_front();

4.记录答案

1
2
if(i>=k-1)
            res.push_back(nums[q.front()]);

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q;
        vector<int> res;
        for(int i=0;i<nums.size();i++)
        {
            while(!q.empty()&&nums[i]>nums[q.back()])
                q.pop_back();
            q.push_back(i);
            if(i-q[0]+1>k)
                q.pop_front();
            if(i>=k-1)
                res.push_back(nums[q.front()]);
        }
        return res;
    }
};

单调队列记录对应元素的下标而不是这个元素原因

下面是我自己写的代码，很明显不对

我是用队列存储元素，对应上面的四个步骤

1.删除操作

if里面删除的是 2 1 4这种情况

else 里面删除的是 4 2 3的2这种情况

2.入队

删完了直接入队

3.检查队列大小

我是直接用队列大小来检查队首是否滑出窗口，这显然不对

比如 4 2 3这种情况

已经把2删了只剩下 4 3当然队列大小当然比3小了，但是4已经不是窗口内了，所以导致了错误

4.记录答案

所以问题最大的就是检查队首有没有滑出队列

但是这个时候就发现，除了用队列大小也没其他方法，因为我们不知道队列首部那个元素的下标，也没法计算当前元素到队首的元素的距离，所以最好用队列存储元素的下标而不是相应的元素

其次的话两个删除操作可以二合一，这个可以改进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q;
        vector<int> res;
        for(int i=0;i<nums.size();i++)
        {
            if(!q.empty()&&nums[i]>q.front())
            {
                while(!q.empty())
                    q.pop_front();
                q.push_back(nums[i]);
            }
            else
            {
                while(!q.empty()&&nums[i]>q.back())
                    q.pop_back();
                q.push_back(nums[i]);  
            }
            while(q.size()>k)
                    q.pop_front();
            if(i>=k-1)
                res.push_back(q.front());
        }
        return res;
    }
};

单调队列 滑动窗口最大值【基础算法精讲 27】_哔哩哔哩_bilibili

参考的灵神的视频，大家可以看看

347.前K个高频元素

347. 前 K 个高频元素 - 力扣（LeetCode）

解法1：哈希+排序

很明显用map，key就是nums[i]，val就是出现次数

然后根据val排序，输出前k个元素即可

需要注意的是自己写排序函数和把map转换成vector才能排序，没什么难点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool static cmp(pair<int,int> a,pair<int,int> b)
    {
        return a.second>b.second;
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> p;
        vector<int> res;
        for(auto c:nums)
            p[c]++;
        vector<pair<int,int>> v(p.begin(),p.end());
        sort(v.begin(),v.end(),cmp);
        for(int i=0;i<k;i++)
            res.push_back(v[i].first);
        return res;
    }
};

解法2：优先级队列

首先要解决使用大顶堆还是小顶堆的问题

如果使用大顶堆，大的排在前面，在我们要加入新的元素的时候要进行弹出元素，那么大的元素就被弹出了，所以到最后我们求出来的其实是前K小的元素，而不是前K大的元素，所以要用小顶堆

思路:

先用map统计出现的频率，然后将map的元素pair对加入小顶堆，如果小顶堆的元素数量超过了k那就弹出一个元素，弹出去的一定是元素出现频率更小的元素，到最后小顶堆中只剩下前K个高频元素，把高频元素输出即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    class cmp {
    public:
        bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
            return a.second > b.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> p;
        vector<int> res;
        for(auto c:nums)
            p[c]++;
        priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> q;
        for(auto c:p)
        {
            q.push(c);
            if(q.size()>k)
                q.pop();
        }
        while(k--)
        {
            res.push_back(q.top().first);
            q.pop();
        }
        return res;
    }
};

个人觉得不如就用哈希加map排序….

这个是对前K个进行排序，哈希是全部的进行排序