239. 滑动窗口最大值
一开始本来想用优先队列和队列这两个数据结构来储存数，但后来发现优先队列实现不了移除数据。所以改用了map。但一运行发现时间超了。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
queue<int> que;
vector<int> res;
map<int,int> q_map;
for(int i=0; i<k-1; i++){
que.push(nums[i]);
auto old_it = q_map.find(nums[i]);
if(old_it != q_map.end()){
old_it->second++;
}
else{
q_map.emplace(make_pair(nums[i],1));
}
}
for(int i=k-1; i<nums.size(); i++){
que.push(nums[i]);
auto old_it = q_map.find(nums[i]);
if(old_it != q_map.end()){
old_it->second++;
}
else{
q_map.emplace(make_pair(nums[i],1));
}
auto it = q_map.rbegin();
while(it != q_map.rend()){
if(it->second > 0){
res.push_back(it->first);
break;
}
it++;
}
int opt_num = que.front();
que.pop();
auto new_it = q_map.find(opt_num);
if(new_it != q_map.end()){
new_it->second --;
}
else{
cout<<"wrong"<<endl;
}
}
return res;
}
};
费劲巴力的连抄带蒙的写出来了，还是有点不太理解单调队列。单调队列的原理大概是明白了，但是还是懂得不透彻。
class Solution {
private:
class Myqueue{
public:
deque<int> que;
void pop(int val){
if(!que.empty() && que.front()== val){
que.pop_front();
}
}
void push(int val){
while(!que.empty() && val>que.back()){
que.pop_back();
}
que.push_back(val);
}
int front(){
return que.front();
}
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
Myqueue que;
vector<int> res;
for(int i=0; i<k; i++){
que.push(nums[i]);
}
res.push_back(que.front());
for(int i=k; i<nums.size(); i++){
que.pop(nums[i-k]);
que.push(nums[i]);
res.push_back(que.front());
}
return res;
}
};
第二天早上又把这道题凭着记忆，又带着理解重新写了一遍。对三个function的实现还是不够透彻，if还是while用的稀里糊涂，凭记忆的含量偏多。
347.前 K 个高频元素
学得稀里糊涂，基本是把答案抄了一遍。首先是对priority_queue的架构和使用不太清楚，不会写怎么comparsion。然后是不太会怎么实现。还得多做几遍才行。
class Solution {
public:
class mycomparsion{
public:
bool operator()(const pair<int,int>& lhs, const pair<int,int>& rhs){
return lhs.second> rhs.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> umap;
for (int i = 0; i < nums.size(); i++) {
umap[nums[i]]++;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparsion> pri_que;
for(auto it=umap.begin(); it!=umap.end(); it++){
pri_que.push(*it);
if(pri_que.size()>k){
pri_que.pop();
}
}
vector<int> res(k);
for(int i=k-1; i>=0; i--){
res[i] = pri_que.top().first;
pri_que.pop();
}
return res;
}
};
