代码随想录第十天|150.逆波兰表达式求值 239.滑动窗口的最大值 347.前K个高频元素

150.逆波兰表达式求解

思路：做过 使用stoi ：字符串转数字

class Solution {
public:int cal(int num1,int num2,char c){int res;if(c=='+'){res=num1+num2;}if(c=='-'){res=num2-num1;}if(c=='*'){res=num1*num2;}if(c=='/'){res=num2/num1;}return res;}int evalRPN(vector<string>& tokens) {stack<int> st;for(string s:tokens){//说明是数字 注意负数判定if(s[0]>='0'&&s[0]<='9'||(s[0]=='-'&&s[1]>='0'&&s[1]<='9')){st.push(stoi(s));}else{int num1=st.top();st.pop();int num2=st.top();st.pop();st.push(cal(num1,num2,s[0]));}}return st.top();}
};

239.滑动窗口的最大值

思路：使用了单调队列 没太理解 看完视频 差不多明白了 文字版写的不太全 就是自己利用底层容器deque构建一个单调队列 pop代表最左边元素 push代表最右边元素  pop元素如果不是当前队头元素 说明已经被pop掉 因为要维护单调队列  push 的时候前面比当前元素小的都要pop O(n)时间复杂度遍历实现 

class Solution {
public:class MyQueue{public:deque<int> que;//双向队列//弹出最左边元素void pop(int value){//value为要弹出的元素 如果元素不相等 说明之前被弹出了 不需要弹出if(!que.empty()&&value==que.front())que.pop_front();}//维护递减队列 后面大删除void push(int value){while(!que.empty()&&que.back()<value)que.pop_back();que.push_back(value);}int front(){return que.front();}};vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> result;MyQueue que;//初始化for(int i=0;i<k;i++)que.push(nums[i]);result.push_back(que.front());//i代表要push进来的元素for(int i=k;i<nums.size();i++){que.pop(nums[i-k]);que.push(nums[i]);result.push_back(que.front());}return result;} 
};

347.前K个高频元素

思路：

map记录

priority_queue 排序

巧妙思路 排序小顶堆 好题 还联系容器的使用和优先队列

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> map;for(int i=0;i<nums.size();i++){map[nums[i]]++;}  //利用小顶堆排序最小的priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparsion> pri_que;for(unordered_map<int,int>::iterator it=map.begin();it!=map.end();it++){pri_que.push(*it);//遍历所有的元素 插入n个 弹出 n-k个 剩余k个最大的 if(pri_que.size()>k){pri_que.pop();}}vector<int> result(k);//倒序输出for (int i = k - 1; i >= 0; i--) {result[i] = pri_que.top().first;pri_que.pop();}return result;}
};