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;
}
};
网友评论