力扣题解(队列）

933. 最近的请求次数

构建一个请求队列，之前的请求与当前请求时间间隔大于 3000 ms 的出队列，最后返回队列的长度即可。

class RecentCounter {
private: 
    queue<int> q;

public:
    RecentCounter() {
    
    }
    
    int ping(int t) {
        q.push(t);
        while(!q.empty() && q.front() < t - 3000) {
            q.pop();
        }
        return q.size();
    }
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */

面试题59 - I. 滑动窗口的最大值

双向队列

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> dq;
        vector<int> res;
        if(n < k)
            return res;
        // 每一轮要做的事情：
            // 1 检查最左侧的元素是否需要退场
            // 2 把最大的数对应的下标放在双向队列的最左端，如果左边下标的元素小于当前元素，则清除左边下标的元素
            // 3 输出双向队列最左端下标对应的元素
        for(int i = 0; i < n; ++i) {
            // 检查最左侧的元素是否需要退场
            while(!dq.empty() && i - dq.front() +1 > k)
                dq.pop_front();
            // 把最大的数对应的下标放在双向队列的最左端，如果左边下标的元素小于当前元素，则清除左边下标的元素
            while(!dq.empty() && nums[dq.back()] <= nums[i])
                dq.pop_back();
            dq.push_back(i);
            // 输出双向队列最左端下标对应的元素
            if (i >= k - 1)
                res.push_back(nums[dq.front()]);
        }
        return res;       
    }
};

347. 前 K 个高频元素

优先队列

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> res;
        unordered_map<int, int> mp;
        // 默认大顶堆
        priority_queue<pair<int, int> > pq;
        for (auto num: nums)
            mp[num] ++;
        for (auto p: mp) {
            pq.push (pair<int, int>(-p.second, p.first));
            if (pq.size() > k)
                pq.pop();
        }
        while(k--) {
            res.push_back(pq.top().second);
            pq.pop();
        }
        return res;
    }
};