150. 逆波兰表达式求值文章链接 完成情况看完逆波兰表达式原理自己想出了思路15minAC思路遍历字符串遇到加减乘除就从栈里弹出两个值进行计算再进入栈是数字就继续入栈最后弹出栈顶就是最后计算结果注意事项stoi()-转换为int、stol()-转换为long、stoll()-转换为long long、stoul()-转换为unsigned long、stoull()-转换为unsigned long longint evalRPN(vectorstring tokens) { stacklong long st; for(auto i:tokens){ if(i||i-||i*||i/){ int b st.top(); st.pop(); int a st.top(); st.pop(); if(i) st.push(ab); else if(i-) st.push(a-b); else if(i*) st.push(a*b); else if(i/) st.push(a/b); }else{ st.push(stoll(i)); } } return st.top(); }239. 滑动窗口最大值文章链接 完成情况看文章视频花费约1hAC本题学习了使用双向队列构造新功能列其常用函数为push_front(); pop_front(); push_back(); pop_back(); front(); back()思路本题构造了新功能列列包含pop、push和front函数其中push规则为如果push值大于队尾元素删除队尾直到push值前面没有比它大的值该操作可以实现队列元素始终降序排放pop函数规则为判断队头是否是要删除的值判断好之后再删因为push操作会提前删掉本来就应该删的元素front函数无处理就是弹出队头但由于队列元素降序排放所以队头就是最大值题目函数中执行先push前k个元素返回队头得到第一个结果放入result数组-从k开始遍历数组每次执行pop窗口左边元素push窗口右边元素返回front。class MyQueue{ public: dequeint qe; void pop(int v){ if(!qe.empty() vqe.front()) qe.pop_front(); //因为队列降序排列所以比队头小的元素已经提前删掉所以在删除元素时要判断是不是真的要pop队头若要删除的元素队头则确实应该删掉再删如果不等于队头则说明已经删过了则无需处理 } void push(int v){ while(!qe.empty() vqe.back()) qe.pop_back();//保证新进元素前面没有比自己大的元素也就是队列元素降序排列 qe.push_back(v);//判断完前面没有比自己大的元素之后在加入此元素 } int front(){ return qe.front();//由于队列降序排列则直接返回队头即可 } }; public: vectorint maxSlidingWindow(vectorint nums, int k) { MyQueue qe; vectorint result; for(int i0;ik;i){ qe.push(nums[i]); } result.push_back(qe.front()); for(int i k;inums.size();i){ qe.pop(nums[i-k]);//每次滑动时删除窗口最左边值 qe.push(nums[i]);//加上窗口新值 result.push_back(qe.front()); } return result; }347.前 K 个高频元素文章链接 完成情况看视频文章花费约45min本题使用了哈希表map用来存放数字以及出现频率然后使用小顶堆进行前k个高频元素存放思路遍历数组mp[数字]达到记录数字及其出现频率的作用然后遍历mp元素依次进入堆(优先级队列)中当堆元素超过k时就弹出一次(需要弹出最小值所以用小顶堆)最后将堆元素倒序放入数组result中注意事项-堆定义class mycomparison{ public: bool operator()(const pairint,int l,const pairint,int r){ return l.secondr.second;//如果左大于右返回true 该方式实现的是小顶堆 } } priority_queuepairint,int,vectorpairint,int,mycomparison pri_que; //中第一个数元素类型第二个是以什么容器存放元素一般默认就是vector固定写法最后是比较方法实现大顶堆还是小顶堆依据pair的第一还是第二部分排序class Solution { public: class mycomparison{ public: bool operator()(const pairint,int l,const pairint,int r){ return l.secondr.second; } }; vectorint topKFrequent(vectorint nums, int k) { unordered_mapint,int myMap; for(int i:nums) myMap[i]; priority_queuepairint,int,vectorpairint,int,mycomparison pri_que; for(auto pr:myMap){ pri_que.push(pr); if(pri_que.size()k) pri_que.pop(); } vectorint result(k); for(int i k-1;i0;i--){ result[i] pri_que.top().first; pri_que.pop(); } return result; } };总结栈和队可以互相实现栈很适合解决匹配问题比如左右运算符、相邻元素相同删除、逆波兰运算问题双向队列的前后获取、push和弹出很适合解决滑动窗口维护最大值的问题堆(优先级队列)适合解决对无序数据取k个最值的问题。