代码随想录算法训练营Day-11 | 150. 逆波兰表达式求值、239. 滑动窗口最大值、 347.前 K 个高频元素-北京尧图网络

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个最值的问题。

代码随想录算法训练营Day-11 | 150. 逆波兰表达式求值、239. 滑动窗口最大值、 347.前 K 个高频元素

相关推荐

推荐系统特征工程管线的自动化：从手写 SQL 到 Feature Store 的工程演进与一致性保障

Redis的string类及基础指令

广告 CTR 预估模型的 GPU 推理优化：大规模稀疏特征 Embedding 的显存管理与混合精度计算

更多资讯

LobeHub 配置 OPENAI_PROXY_URL 后返回空白消息怎么排查？

AFFiNE 拉取最新 canary 后应用无法启动怎么排查？重跑依赖安装与 native 构建

AI“差不多先生”：幻觉、套壳与落地之殇

SNMP测试工具全解析：从协议基础到排障实战

HBase迁移方案设计：跨版本升级、跨集群迁移与数据校验

用 `CD_DEPLOY_ENABLED` 变量为 PostHog 生产构建与部署工作流加闸门（Gating）

今日更新

在S3C2410上移植Nucleus RTOS：启动、驱动与实时性调优实战

2026年Turnitin降重降AI二合一红黑榜：能过和别碰

2026期刊投稿AI写作工具实测：6款打分谁更值得用

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？