当前位置：首页 > news >正文

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

news 来源：原创 2025/8/18 18:19:17

150.逆波兰表达式求值：

文档讲解：代码随想录|150.逆波兰表达式求值

视频讲解：栈的最后表演！ | LeetCode：150. 逆波兰表达式求值_哔哩哔哩_bilibili

状态：已做出

思路：

这道题目是让我们按照逆波兰表达式来求值，逆波兰表达式可以使用栈的先进后出的形式来求值，因为根据给出的案列可以看出每次遍历到算数运算符后就会排出最后两个数来和运算符进行运算，运算后把值还要进行随后的操作，按照这个特点可以看得出来和栈的特性一样，只要每次把容器中的数字字符串转化为数字，遇到运算符后拿出栈的两个数运算把得出的值再次放入栈中，循环往复，最后栈里的数就是最终运算的结果，返回栈的栈顶元素既可，这时栈的元素绝对只有一个。
代码如下:

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int>st;//创建栈for(int i=0;i<tokens.size();++i) {int a1,a2,sum;//使用变量a1和a2来分别保存栈最后连个元素//接下来使用四个if语句来对运算符进行操作if(tokens[i]=="+") {a1=st.top();//保存栈顶也就是最后一个元素st.pop();//删除栈顶元素a2=st.top();//保存删除最后一个元素后的栈顶元素st.pop();//继续删除sum=a1+a2;st.push(sum);}else if(tokens[i]=="-") {a1=st.top();st.pop();a2=st.top();st.pop();sum=a2-a1;st.push(sum);}else if(tokens[i]=="*") {a1=st.top();st.pop();a2=st.top();st.pop();sum=a2*a1;st.push(sum);}else if(tokens[i]=="/") {a1=st.top();st.pop();a2=st.top();st.pop();sum=a2/a1;st.push(sum);}else {st.push(stoi(tokens[i]));//如果不是运算符就使用stoi库函数把字符串直接变成int型插入到栈中}}//在前面的循环结束后栈中的元素绝对只有一个元素，就是运算后的结果，直接返回栈顶元素即可return st.top();//}
};

遇到的困难：

这道题目就是考察对栈的应用，只要能够想到使用栈本题就没有什么问题，唯一要注意的就是每次运算后的值要放入栈里，继续参与后续的运算。

收获：

通过此题的联系认识了逆波兰表达式，逆波兰表达式能在不使用括号的情况下正确的计算出运算符的优先级，这样就能让计算机更加快捷的实现计算，不用去找括号来判断运算符的优先级。

239.滑动窗口最大值：

文档讲解：代码随想录|239.滑动窗口最大值

视频讲解：单调队列正式登场！| LeetCode：239. 滑动窗口最大值_哔哩哔哩_bilibili

状态：已做出

思路：

这道题目是使用单调队列，难度有点大，我模仿文档的代码一开始用单调队列保存了数组中的元素，结果出错了，后来让ai对我的代码进行修改，才知道可以让单调队列保存数组的下标，这样在后续删除滑动窗口以外的元素直接使用单调队列里的下标来判断比判断元素要更加方便不容易出错。单调队列的大致使用思路就是让数组保存每个数组中的下标，当队列的第一个元素保存的下标不属于窗口时进行头删，每次插入数组下标时判断这这个下标元素是否大于队列里保存下标位置的元素，删除比此时数组下标元素小的所有队列保存的数组下标，让整个队列里的下标都是按照下标元素从大到小单调保存，这样每次对头都是此时窗口的最大值，每次只要保存对头下标指向的数组元素就返回这一系列的目标数组既可。文档给出的代码更加直观，逻辑更加清晰，我是按照文档的思路把全部功能在一个循环里实现了，可能不太直观。
因为最终代码是ai改善的，所以一下是ai修改的代码:

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {deque<int> dq;  // 存储的是索引vector<int> result;for (int i = 0; i < nums.size(); ++i) {// 移除出窗口的索引，使用单调队列保存的索引来和滑动窗口最前面一个位置的索引进行比较if (!dq.empty() && dq.front() <= i - k) {dq.pop_front();}// 维护单调递减队列（从大到小），只要需要插入的索引代表的元素大于队列前面索引对应的元素，就删除，保证队列整体处于单调递减while (!dq.empty() && nums[i] >= nums[dq.back()]) {dq.pop_back();}dq.push_back(i);// 添加窗口最大值if (i >= k - 1) {result.push_back(nums[dq.front()]);}}return result;}
};

遇到的困难：

这道题目使用单调队列是保证队列里的元素保存顺序为单调递减的，实现这个操作其实不难，使用循环一个一个判断删除就行，但是当时最让我不理解的是怎么正确的判断出滑动窗口移动后需要删除的元素，一开始本打算直接用滑动窗口的最后以为元素来和单调队列对头元素进行对比来进行删除，但想实现这个操作还要额外用一个遍历来保存滑动窗口第一个位置下标，操作不太好控制，最后ai给我建议是让单调队列保存数组下标，用下标来判断是否要删除队头元素，这样设计比直接判断元素更加简便，后来通过ai改善的代码才解决了题目。

收获：

这道题目我第一次接触单调队列，通过练习了解了单调队列的特性和解题技巧，单调队列的设计操作本身其实不难，但是这道题目给出的要求要控制单调队列对头元素在非滑动窗口外就删除，这才是本体的难点，学习到了控制单调队列的方法。

347.前k个高频元素：

文档讲解：代码随想录|347.前k个高频元素

视频讲解：优先级队列正式登场！大顶堆、小顶堆该怎么用？| LeetCode：347.前 K 个高频元素_哔哩哔哩_bilibili

状态：已做出

思路：

这道题目的主要思路根据文档使用的优先队列来解决的。优先队列的特性是每次插入值后都会默认排序，这题是计算数组中元素的频率，所以使用map来保存元素的出现次数比较合适，优先队列使用小顶堆用仿函数来实现优先队列里的排序规则，优先队列里的元素是pair，用来存储map里的元素。使用小顶堆是为了让最小的出现次数排在队列前面，随后判断此时队列插入的元素个数是否大于题目给的k，大于就删除对头的元素，这样不断判断不断删除，让优先队列的元素个数保持在k个，最后讲这个优先队列里的first元素全部保存在vector容器中并返回既可。
代码如下:

class Solution {
public://设置仿函数来对优先队列进行自定义排序class Mypair{public:bool operator()(pair<int,int>&a1,pair<int,int>&a2) {//这里设置和sort的bool类型自定义排序有不同，这里是大于符号指向那一边，哪一边优先度就大，而前面a1默认就是较小值，较小值优先度大就说明是小顶堆return a1.second>a2.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int>mp;//设置map来计算每个元素的出现次数//循环保存元素频率for(int i=0;i<nums.size();++i) {++mp[nums[i]];}priority_queue<pair<int,int>,vector<pair<int,int>>,Mypair>pq;//实现自定义的小顶堆优先队列//使用迭代器遍历unoedered_map容器把元素保存在优先队列中for(unordered_map<int,int>::iterator it=mp.begin();it!=mp.end();++it) {pq.push(*it);//当不同元素的个数大于k时需要把对头元素删除，这样就能准确的删除较小的频率元素，最后保存的就是前k高频元素if(pq.size()>k) {pq.pop();}}vector<int>relue;//使用循环把优先队列里的所有元素都保存在数组里并返回此数组for(int i=0;i<k;++i) {relue.push_back(pq.top().first);pq.pop();}return relue;}
};

遇到的困难：

这道题目的难点首先就是要想到优先队列，使用优先队列就是因为由优先队列插入的排序和删除元素时间复杂度都是logn，可以让后续删除和插入操作时间更优。还有一个难点就是要正确设计仿函数来改变优先队列的排序方式，只要仿函数设计正确了，后续使用优先队列既可。

收获：

通过这道题目可以体验到优先队列的特性和优势，还顺便复习了一下仿函数的设计，优先队列的优势就在于能在插入的同时动态的进行排序，并且排序的时间复杂度很小，这样能大大减少后续的操作，也进一步实践认识了仿函数的设计思路。

150.逆波兰表达式求值：

思路：

遇到的困难：

收获：

239.滑动窗口最大值：

思路：

遇到的困难：

收获：

347.前k个高频元素：

思路：

遇到的困难：

收获：

相关文章：