239. 滑動窗口最大值
題目鏈接：
https://leetcode.cn/problems/sliding-window-maximum/
算法思想
使用隊列實現(xiàn)滞谢。最簡單的思路就是雙重循環(huán)擎颖，時間復雜度是nxk扔罪，超時做瞪。
可以使用雙頭隊列deque實現(xiàn)妹田。自定義一個雙頭隊列带膀，隊列中維護一組單調遞減的數(shù)據(jù)，每次獲取最大值，只要獲取隊頭的值即可香嗓。
代碼：
class Solution {
public:
? ? class max_queue{
? ? ? ? private:
? ? ? ? ? ? deque<int> d;
? ? ? ? public:
? ? ? ? void pop(int value) {
? ? ? ? ? ? if (!d.empty() && value == d.front()) {
? ? ? ? ? ? ? ? d.pop_front();
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? ? ? void push(int val)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? while(!d.empty() && d.back() < val)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? // cout<<"d.pop_front:"<<d.front()<<endl;
? ? ? ? ? ? ? ? ? ? d.pop_back();
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? d.push_back(val);
? ? ? ? ? ? ? ? // cout<<"d.push_back"<<val<<endl;
? ? ? ? ? ? }
? ? ? ? ? ? int get_max_val()
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return d.front();
? ? ? ? ? ? }
? ? ? ? };
? ? vector<int> maxSlidingWindow(vector<int>& nums, int k) {
? ? ? ? max_queue? max_q;
? ? ? ? int len = nums.size();
? ? ? ? vector<int> res;
? ? ? ? for(int i=0;i<k;i++)
? ? ? ? {
? ? ? ? ? ? max_q.push(nums[i]);
? ? ? ? }
? ? ? ? int max_value = max_q.get_max_val();
? ? ? ? ? ? // cout<<"max_value:"<<max_value<<endl;
? ? ? ? res.push_back(max_value);
? ? ? ? for(int i=k;i<len;i++)
? ? ? ? {
? ? ? ? ? ? cout<<"i:"<<i<<endl;
? ? ? ? ? ? max_q.pop(nums[i-k]);
? ? ? ? ? ? max_q.push(nums[i]);
? ? ? ? ? ? int max_value = max_q.get_max_val();
? ? ? ? ? ? // cout<<"max_value:"<<max_value<<endl;
? ? ? ? ? ? res.push_back(max_value);
? ? ? ? }
? ? ? ? return res;
? ? }
};
347. 前 K 個高頻元素
代碼鏈接：https://leetcode.cn/problems/top-k-frequent-elements/
算法思路：
最前k的最大頻率元素迅腔。
首先使用map進行頻率的統(tǒng)計，
其次靠娱，維護一個k個元素的小頂堆沧烈。為什么使用小頂堆呢？因為小頂堆pop()的時候像云，彈出最小元素锌雀，最后就留了前k個大的元素。
代碼：
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> m;
? ? ? ? int len = nums.size();
? ? ? ? for(int i=0;i<len;i++)
? ? ? ? {
? ? ? ? ? ? if(m.find(nums[i])==m.end())
? ? ? ? ? ? ? ? m[nums[i]] = 0;
? ? ? ? ? ? m[nums[i]] += 1;
? ? ? ? }
? ? ? ? priority_queue<pair<int,int>, vector<pair<int,int>>, mycomparison> pri;
? ? ? ? for(unordered_map<int,int>::iterator it = m.begin();it!=m.end();it++)
? ? ? ? {
? ? ? ? ? ? pri.push(*it);
? ? ? ? ? ? if(pri.size()>k)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? pri.pop();
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? vector<int> result(k);
? ? ? ? for(int i=0;i<k;i++)
? ? ? ? {
? ? ? ? ? ? result[i] = pri.top().first;
? ? ? ? ? ? pri.pop();
? ? ? ? }
? ? ? ? return result;
? ? }
};
