美文网首页
力扣题解(队列)

力扣题解(队列)

作者: 衣介书生 | 来源:发表于2020-03-04 00:14 被阅读0次

    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;
        }
    };
    

    相关文章

      网友评论

          本文标题:力扣题解(队列)

          本文链接:https://www.haomeiwen.com/subject/trqdlhtx.html