KEY1语法用法详细见下2用deque实现单调队列3用堆实现寻找前k大的元素用priority_queue实现堆1语法用法详细vector假设我们定义了一个vectorint vec;增添加元素push_back(val): 在数组末尾添加一个元素。相当于自动执行了realloc如果空间不够。insert(it, val): 在指定位置插入元素涉及元素后移效率较低。删删除元素pop_back(): 删除最后一个元素。erase(it): 删除指定位置的元素涉及元素前移。clear(): 清空所有元素但通常不释放内存。查访问与大小vec[i]: 下标访问。不检查越界和 C 一样快。vec.at(i): 访问元素。会检查越界如果越界会抛出异常更安全。**front()/back()**: 获取第一个和最后一个元素的引用。size(): 当前数组里存了多少个元素相当于 C 里的count。empty(): 返回布尔值判断是否为空。2. 内存管理C 程序员最关心的这是vector最精华的部分解决了 C 语言中频繁realloc的痛苦。capacity(): 容器当前实际分配的内存大小。reserve(n):预留空间。场景如果你知道要存 1000 个数先reserve(1000)这样后续push_back就不会触发多次内存重分配realloc极大地提高性能。resize(n):改变大小。这不仅改空间还会创建n个对象。如果n比当前大新位置会填 0。queue函数功能描述复杂度push(val)在队尾添加一个元素O(1)O(1)O(1)pop()删除队首元素注意不返回该值O(1)O(1)O(1)front()返回队首元素的引用O(1)O(1)O(1)back()返回队尾元素的引用O(1)O(1)O(1)empty()检查队列是否为空O(1)O(1)O(1)size()返回队列中元素的个数O(1)O(1)O(1)deque基础操作表类别函数功能复杂度头部操作push_front(),pop_front()在队头插入或删除O(1)O(1)O(1)尾部操作push_back(),pop_back()在队尾插入或删除O(1)O(1)O(1)随机访问operator[],at()访问指定索引元素O(1)O(1)O(1)首尾访问front(),back()获取首尾元素引用O(1)O(1)O(1)容量size(),empty()查看大小或判空O(1)O(1)O(1)150. 逆波兰表达式求值没啥就是用栈实现计算。整个代码class Solution{public:intevalRPN(vectorstringtokens){//用栈实现stacklonglongst;for(inti0;itokens.size();i){if(tokens[i]||tokens[i]-||tokens[i]*||tokens[i]/){longlongast.top();st.pop();longlongbst.top();st.pop();if((tokens[i]){st.push(ba);}if((tokens[i]-){st.push(b-a);}if((tokens[i]*){st.push(b*a);}if((tokens[i]/){st.push(b/a);}}else{st.push(tokens[i]);}}returnst.top();}};239. 滑动窗口最大值1思路用单调队列用deque实现注意单调队列中相等的元素也要保留不然会出问题注意public和private的用法整个代码class Solution{private:class myque{public:dequeintque;voidpop(intval){if(!que.empty()que.front()val){que.pop_front();}}voidpush(intval){//注意这里要维护一个单调队列也就是队列从前到后是从大到小的。所以每个新来的元素都加到队尾和自己前面的那个元素比如果前面那个元素小就pop前面那个元素直到前面那个元素比自己大//注意这里不能写, 因为这样的话比如现在窗口里的数是[7,5,7,1]队列里是[7,1]那窗口往后移动一格后会pop前面那个7但是这在队列里就把第二个7也pop掉了不对。所以即使两个数字一样大也都得留在队列里因为pop的时候只能pop前面的那个while(!que.empty()que.back()val){que.pop_back();}que.push_back(val);}intfront(){returnque.front();}};public:vectorintmaxSlidingWindow(vectorintnums,intk){myque que;vectorintresult;for(inti0;ik;i){que.push(nums[i]);}result.push_back(que.front());for(inti1;ik-1nums.size();i){que.pop(nums[i-1]);que.push(nums[ik-1]);result.push_back(que.front());}returnresult;}};347.前 K 个高频元素1用什么数据结构存每个元素的出现次数用mapkey,value, key是元素value是出现次数2寻找前k大的元素小顶堆节点个数为k因为每次Pop的都是堆顶元素所以堆中维护的是前k大的元素3堆用priority_queue来实现。要会priority_queue的语法。eg.如何写比较函数class mycomparison{public:booloperator()(constpairint,intlhs,constpairint,intrhs){//返回优先级小的小顶堆的话大元素在下面优先级小所以左边的大的话就返回truereturnlhs.secondrhs.second;}};整个代码class Solution{public:class mycomparison{public:booloperator()(constpairint,intlhs,constpairint,intrhs){//返回优先级小的小顶堆的话大元素在下面优先级小所以左边的大的话就返回truereturnlhs.secondrhs.second;}};vectorinttopKFrequent(vectorintnums,intk){unordered_mapint,intmap;for(inti0;inums.size();i){map[nums[i]];}priority_queuepairint,int,vectorpairint,int,mycomparisonpri_que;for(unordered_mapint,int::iterator itmap.begin();it!map.end();it){pri_que.push(*it);if(pri_que.size()k){pri_que.pop();}}//注意要实现声明容器大小才能访问result[i]vectorintresult(k);for(intik-1;i0;i--){result[i]pri_que.top().first;pri_que.pop();}returnresult;}};详细信息第五章 栈与队列part02逆波兰表达式求值本题不难但第一次做的话会很难想到所以先看视频了解思路再去做题题目链接/文章讲解/视频讲解https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html滑动窗口最大值 有点难度可能代码写不出来但一刷至少需要理解思路之前讲的都是栈的应用这次该是队列的应用了。本题算比较有难度的需要自己去构造单调队列建议先看视频来理解。题目链接/文章讲解/视频讲解https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html347.前 K 个高频元素 有点难度可能代码写不出来一刷至少需要理解思路大/小顶堆的应用 在C中就是优先级队列本题是 大数据中取前k值 的经典思路了解想法之后不算难。题目链接/文章讲解/视频讲解https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html总结栈与队列做一个总结吧加油https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E6%80%BB%E7%BB%93.html
代码随想录算法训练营第11天|150. 逆波兰表达式求值 | 239. 滑动窗口最大值 | 347.前 K 个高频元素
发布时间：2026/5/27 3:35:21
KEY1语法用法详细见下2用deque实现单调队列3用堆实现寻找前k大的元素用priority_queue实现堆1语法用法详细vector假设我们定义了一个vectorint vec;增添加元素push_back(val): 在数组末尾添加一个元素。相当于自动执行了realloc如果空间不够。insert(it, val): 在指定位置插入元素涉及元素后移效率较低。删删除元素pop_back(): 删除最后一个元素。erase(it): 删除指定位置的元素涉及元素前移。clear(): 清空所有元素但通常不释放内存。查访问与大小vec[i]: 下标访问。不检查越界和 C 一样快。vec.at(i): 访问元素。会检查越界如果越界会抛出异常更安全。**front()/back()**: 获取第一个和最后一个元素的引用。size(): 当前数组里存了多少个元素相当于 C 里的count。empty(): 返回布尔值判断是否为空。2. 内存管理C 程序员最关心的这是vector最精华的部分解决了 C 语言中频繁realloc的痛苦。capacity(): 容器当前实际分配的内存大小。reserve(n):预留空间。场景如果你知道要存 1000 个数先reserve(1000)这样后续push_back就不会触发多次内存重分配realloc极大地提高性能。resize(n):改变大小。这不仅改空间还会创建n个对象。如果n比当前大新位置会填 0。queue函数功能描述复杂度push(val)在队尾添加一个元素O(1)O(1)O(1)pop()删除队首元素注意不返回该值O(1)O(1)O(1)front()返回队首元素的引用O(1)O(1)O(1)back()返回队尾元素的引用O(1)O(1)O(1)empty()检查队列是否为空O(1)O(1)O(1)size()返回队列中元素的个数O(1)O(1)O(1)deque基础操作表类别函数功能复杂度头部操作push_front(),pop_front()在队头插入或删除O(1)O(1)O(1)尾部操作push_back(),pop_back()在队尾插入或删除O(1)O(1)O(1)随机访问operator[],at()访问指定索引元素O(1)O(1)O(1)首尾访问front(),back()获取首尾元素引用O(1)O(1)O(1)容量size(),empty()查看大小或判空O(1)O(1)O(1)150. 逆波兰表达式求值没啥就是用栈实现计算。整个代码class Solution{public:intevalRPN(vectorstringtokens){//用栈实现stacklonglongst;for(inti0;itokens.size();i){if(tokens[i]||tokens[i]-||tokens[i]*||tokens[i]/){longlongast.top();st.pop();longlongbst.top();st.pop();if((tokens[i]){st.push(ba);}if((tokens[i]-){st.push(b-a);}if((tokens[i]*){st.push(b*a);}if((tokens[i]/){st.push(b/a);}}else{st.push(tokens[i]);}}returnst.top();}};239. 滑动窗口最大值1思路用单调队列用deque实现注意单调队列中相等的元素也要保留不然会出问题注意public和private的用法整个代码class Solution{private:class myque{public:dequeintque;voidpop(intval){if(!que.empty()que.front()val){que.pop_front();}}voidpush(intval){//注意这里要维护一个单调队列也就是队列从前到后是从大到小的。所以每个新来的元素都加到队尾和自己前面的那个元素比如果前面那个元素小就pop前面那个元素直到前面那个元素比自己大//注意这里不能写, 因为这样的话比如现在窗口里的数是[7,5,7,1]队列里是[7,1]那窗口往后移动一格后会pop前面那个7但是这在队列里就把第二个7也pop掉了不对。所以即使两个数字一样大也都得留在队列里因为pop的时候只能pop前面的那个while(!que.empty()que.back()val){que.pop_back();}que.push_back(val);}intfront(){returnque.front();}};public:vectorintmaxSlidingWindow(vectorintnums,intk){myque que;vectorintresult;for(inti0;ik;i){que.push(nums[i]);}result.push_back(que.front());for(inti1;ik-1nums.size();i){que.pop(nums[i-1]);que.push(nums[ik-1]);result.push_back(que.front());}returnresult;}};347.前 K 个高频元素1用什么数据结构存每个元素的出现次数用mapkey,value, key是元素value是出现次数2寻找前k大的元素小顶堆节点个数为k因为每次Pop的都是堆顶元素所以堆中维护的是前k大的元素3堆用priority_queue来实现。要会priority_queue的语法。eg.如何写比较函数class mycomparison{public:booloperator()(constpairint,intlhs,constpairint,intrhs){//返回优先级小的小顶堆的话大元素在下面优先级小所以左边的大的话就返回truereturnlhs.secondrhs.second;}};整个代码class Solution{public:class mycomparison{public:booloperator()(constpairint,intlhs,constpairint,intrhs){//返回优先级小的小顶堆的话大元素在下面优先级小所以左边的大的话就返回truereturnlhs.secondrhs.second;}};vectorinttopKFrequent(vectorintnums,intk){unordered_mapint,intmap;for(inti0;inums.size();i){map[nums[i]];}priority_queuepairint,int,vectorpairint,int,mycomparisonpri_que;for(unordered_mapint,int::iterator itmap.begin();it!map.end();it){pri_que.push(*it);if(pri_que.size()k){pri_que.pop();}}//注意要实现声明容器大小才能访问result[i]vectorintresult(k);for(intik-1;i0;i--){result[i]pri_que.top().first;pri_que.pop();}returnresult;}};详细信息第五章 栈与队列part02逆波兰表达式求值本题不难但第一次做的话会很难想到所以先看视频了解思路再去做题题目链接/文章讲解/视频讲解https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html滑动窗口最大值 有点难度可能代码写不出来但一刷至少需要理解思路之前讲的都是栈的应用这次该是队列的应用了。本题算比较有难度的需要自己去构造单调队列建议先看视频来理解。题目链接/文章讲解/视频讲解https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html347.前 K 个高频元素 有点难度可能代码写不出来一刷至少需要理解思路大/小顶堆的应用 在C中就是优先级队列本题是 大数据中取前k值 的经典思路了解想法之后不算难。题目链接/文章讲解/视频讲解https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html总结栈与队列做一个总结吧加油https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E6%80%BB%E7%BB%93.html
