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

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

news 来源：原创 2025/8/19 2:06:23

今日内容：150.逆波兰表达式求值，239.滑动窗口最大值，347.前K个高频元素，栈与队列总结
心得：昨天休息了一天，栈与队列的题都比较典型，之前也是恶补过堆栈的知识，所以做起来相对kmp好一些，理解的比较快。

150.逆波兰表达式求值

自己看到题目的第一想法

用栈来解决问题，遇到运算符就pop出栈顶的两个元素，然后进行运算后将结果重新压入栈。最终栈内的元素就是运算式的结果。

看完代码随想录之后的想法

逆波兰表达式是一种后缀表达式，所谓后缀就是指运算符写在后面。
逆波兰表达式的优点：去掉括号后表达式无歧义；适合用栈操作运算。
时间复杂度: O(n)；
空间复杂度: O(n)。
stoll 是 C++ 标准库中的一个函数，用于将字符串转换为 long long 类型的整数。它的全称是 “string to long long”。
st.push(stoll(tokens[i])); 将tokens[i]转换为整数并压入栈st中。

239.滑动窗口最大值

自己看到题目的第一想法

暴力法当然是双循环依次遍历，记录每个滑动窗口的最大值，时间复杂度为O(n*k)，n是数组长度，k是滑动窗口大小。

看完代码随想录之后的想法

使用单调队列：即单调递减或单调递增的队列。
放进窗口里的元素随着窗口的移动，队列也一进一出；每次移动之后，队列告诉我们里面的最大值是什么。每次窗口移动的时候，调用que.pop(滑动窗口中移除元素的数值)，que.push(滑动窗口添加元素的数值)，然后que.front()就返回我们要的最大值。
队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

设计单调队列的时候，pop，和push操作要保持如下规则：

pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作。
push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止。

每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。
常用的queue在没有指定容器的情况下，deque就是默认底层容器。采用deque来实现单调队列的数据结构。
时间复杂度: O(n)；
空间复杂度: O(k)。

347.前K个高频元素

自己看到题目的第一想法

想用哈希表呃，key是数字，value是出现次数。再按照value大小排序，返回value前k高的key。但是这样时间复杂度就是排序的时间复杂度，最优也是O(nlogn)。

看完代码随想录之后的想法

这道题目主要涉及到如下三块内容：

要统计元素出现频率
对频率排序
找出前K个高频元素

解决方法：

首先统计元素出现的频率，这一类的问题可以使用map来进行统计。
然后是对频率进行排序，这里我们可以使用一种容器适配器就是优先级队列。

优先级队列（堆实现）：
特点：对外接口从队头取元素，从队尾添加元素。内部元素是自动依照元素的权值排列。
缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）
堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。
大顶堆：根节点是最大值。
小顶堆：根节点是最小值。

对于本题，采用小顶堆，每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。解决步骤：

根据出现频率，构建map。
构造小顶堆，将所有频率放入堆中，如果堆的大小大于K值，那么将元素从栈顶推出。
倒序构建数组。

时间复杂度为O(nlogk)，k为前k个高频元素，n为数组大小。空间复杂度为O(n)。

自己实现过程中遇到哪些困难

实现小顶堆必须定义一个比较函数，告诉priority_queue如何比较两个pair<int, int>元素。核心逻辑：
return lhs.second > rhs.second;
定义一个小顶堆：
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

150.逆波兰表达式求值

自己看到题目的第一想法

看完代码随想录之后的想法

239.滑动窗口最大值

自己看到题目的第一想法

看完代码随想录之后的想法

347.前K个高频元素

自己看到题目的第一想法

看完代码随想录之后的想法

自己实现过程中遇到哪些困难

相关文章：