Leetcode 239

整体思想：用一个deque维护滑动窗口中的最大值

滑动窗口移动时，要删除掉最前面的数，并加入一个新的数，当新加入数的前面有小于这个数的值时，要把前面的数都pop掉，直到遇到最大值

deque:

是一个双端队列，存储不一定在连续空间

要用push_back(), push_front(), pop_back(), pop_front()

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {deque<int> que;vector<int> res;for(int i=0; i<k; i++){while(!que.empty() && que.back() < nums[i]){que.pop_back();}que.push_back(nums[i]);}res.push_back(que.front());for(int i=k; i<nums.size(); i++){if(que.front() == nums[i-k]){que.pop_front();}while(!que.empty() && que.back() < nums[i]){que.pop_back();}que.push_back(nums[i]);res.push_back(que.front());}return res;}
};

需要注意的点：第一次遍历完k个值之后，要把deque的第一个数存入res里，不然第一个滑动窗口的值就被略过了

Leetcode 347 Top K Frequent Elements

用哈希表

class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> map;for(int num:nums){map[num]++;}multimap<int, int> orderMap;for(auto iter:map){orderMap.insert(make_pair(iter.second, iter.first));}vector<int> res;for(auto iter = orderMap.rbegin(); iter != orderMap.rend(); iter++){if(k > 0){res.push_back(iter->second);k--;}}return res;}
};

multimap 用key排序，为升序

Priority queue

class Solution {
public:class mycomparison{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> map;for(int num:nums){map[num]++;}priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;for(auto iter = map.begin(); iter != map.end(); iter++){pri_que.push(*iter);if(pri_que.size() > k){pri_que.pop();}}vector<int> res;for(int i=0; i<k; i++){res.push_back(pri_que.top().first);pri_que.pop();}return res;}
};