今天接着补上周末的栈与队列的part2，下午继续完成今天的任务。
150. 逆波兰表达式求值
给你一个字符串数组
tokens，表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*'和'/'。- 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
示例 1：
输入：tokens = ["2","1","+","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
逆波兰表达式相当于是二叉树中的后序遍历。
后序遍历（Postorder Traversal）是指按照 “左子树 - 右子树 - 根节点” 的顺序依次访问二叉树中的节点。也就是说，先递归地遍历左子树，再递归地遍历右子树，最后访问根节点。
实际上逆波兰表达式是为了方便计算机去“理解”，去实现,在这里算法逻辑和 1047. 删除字符串中的所有相邻重复项 类似，消除操作换成了表达式中对应算符的操作，同时计算后的结果要重新压入栈，在二叉树里就相当于是把根节点替换成计算子节点后的值。
如动画所示：
stoll函数
stoll是 C++ 标准库中的一个函数，全称为std::stoll。它的功能是将一个字符串转换为长整型（long long）数值。- 例如，如果有一个字符串
"12345"，通过调用stoll("12345")，它会尝试将这个字符串解析成对应的长整型数值12345。如果字符串表示的内容无法正确转换为长整型（比如包含非数字字符且不符合数值表示规范），那么可能会抛出异常（在没有进行异常处理的情况下）。
class Solution {
public:
int evalRPN(vector<string>& tokens) {
// 力扣修改了后台测试数据，需要用longlong
stack<long long> st;
for (int i = 0; i < tokens.size(); i++) {
if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
long long num1 = st.top();
st.pop();
long long num2 = st.top();
st.pop();
if (tokens[i] == "+") st.push(num2 + num1);
if (tokens[i] == "-") st.push(num2 - num1);
if (tokens[i] == "*") st.push(num2 * num1);
if (tokens[i] == "/") st.push(num2 / num1);
} else {
st.push(stoll(tokens[i]));
//整体遍历逻辑就是，遇到操作数，压入栈，遇到操作符，取出栈顶两个操作数进行操作后再将结果压入。
}
}
int result = st.top();
st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）
return result;
}
};补充：我们学习时较为熟悉的计算表达式为中缀表达式，例如：4 + 13 / 5。但这对于计算机来说，并不是一个很好处理的式子，从左往右读，要判断优先级，要回退到前面继续操作。而后缀表达式对于计算机就十分友好了，可以用栈顺序处理。
239. 滑动窗口最大值
给你一个整数数组
nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
针对这个问题，很容易我们可以想到暴力遍历来解决，但这样的时间复杂度达到了O(n*k)，是不满足要求的。所以我们引入单调队列来解决。
单调队列
- 定义
- 单调队列（Monotonic Queue）是一种特殊的数据结构。它在普通队列的基础上，队列中的元素具有单调性。通常可以分为单调递增队列和单调递减队列。
- 以单调递减队列为例，队列中的元素从队首到队尾是按照从大到小的顺序排列的；单调递增队列则是元素从队首到队尾按照从小到大的顺序排列。
- 操作特点
- 入队操作：
- 当一个新元素要进入单调队列时，需要先将队列中不符合单调性的元素删除，然后再将新元素插入。例如，对于单调递减队列，如果新元素比队尾元素大，那么就将队尾元素依次弹出，直到队尾元素大于新元素或者队列为空，然后再将新元素插入队尾。
- 出队操作：
- 和普通队列类似，单调队列的出队操作也是从队首取出元素。不过在单调队列中，由于元素的单调性，队首元素通常是具有某种最值性质的元素（在单调递减队列中是最大值，单调递增队列中是最小值）。
Deque:
(常用的queue在没有指定容器的情况下，deque就是默认底层容器。)
- 定义与性质
- Deque 是双端队列（Double - Ended Queue）的简称，是 C++ 中的一种序列容器。它的主要特点是可以在队列的两端（头部和尾部）进行高效的插入和删除操作。
- 存储结构
- 其内部存储方式是一种分段连续存储，和连续存储的
vector不同。这种结构使得它在进行头部和尾部操作时不需要像vector那样可能频繁地整体重新分配内存，从而保证了两端操作的高效性。- 元素访问
- 能像
vector一样通过索引访问元素，不过在索引访问速度上比vector稍慢一点。同时，提供了边界检查的访问方式，以避免因越界访问导致程序错误。- 操作特点
- 支持在头部插入（
push_front）和删除（pop_front）元素，以及在尾部插入（push_back）和删除（pop_back）元素。也可以在指定位置插入（insert）和删除（erase）元素。- 容量操作
- 可以获取其大小（
size）、判断是否为空（empty）、调整大小（resize）。- 迭代器支持
- 提供迭代器用于遍历双端队列中的元素。
- 应用场景与比较
- 适用于两端频繁插入和删除元素的场景。和
vector相比，两端操作更高效；和list相比，随机访问更具优势，且两端操作效率也不低。
动画如下：
class Solution {
private:
class MyQueue { //单调队列（从大到小）
public:
deque<int> que; // 使用deque来实现单调队列
// 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
// 同时pop之前判断队列当前是否为空。
void pop(int value) {
if (!que.empty() && value == que.front()) {
que.pop_front();
}
}
// 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
// 这样就保持了队列里的数值是单调从大到小的了。
void push(int value) {
while (!que.empty() && value > que.back()) {
que.pop_back();
}
que.push_back(value);
}
// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
int front() {
return que.front();
}
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MyQueue que;
vector<int> result;
for (int i = 0; i < k; i++) { // 先将前k的元素放进队列
que.push(nums[i]);
}
result.push_back(que.front()); // result 记录前k的元素的最大值
for (int i = k; i < nums.size(); i++) {
que.pop(nums[i - k]); // 滑动窗口移除最前面元素
que.push(nums[i]); // 滑动窗口前加入最后面的元素
result.push_back(que.front()); // 记录对应的最大值
}
return result;
}
};- 时间复杂度: O(n)
- 空间复杂度: O(k)
347.前 K 个高频元素
给你一个整数数组
nums和一个整数k，请你返回其中出现频率前k高的元素。你可以按 任意顺序 返回答案。示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
首先分析题目需求：
- 要统计元素出现频率 = map
- 对频率排序 = 优先级队列
- 找出前K个高频元素
为什么不用快排？
- 快排的局限性
- 数据结构转换成本：
- 当使用快排时，如果数据存储在
map结构中，map通常是基于键值对的关联容器，它的存储方式可能是红黑树（在 C++ 中std::map是红黑树实现）等结构。快排需要一个连续的内存空间来操作，如数组（vector）结构。所以要使用快排，首先需要将map转换为vector，这涉及到数据的复制和重新组织，会带来额外的时间和空间开销。- 排序范围的低效性：
- 快排会对整个数组进行排序。然而在特定场景下，可能只需要维护
k个有序的序列，这意味着快排做了很多可能不必要的工作。例如，如果有一个很大的数据集，但最终只关心其中k个最大值或者最小值组成的有序序列，快排会对整个数据集排序，包括那些不需要的部分，这在时间复杂度上是不高效的。- 优先级队列的优势
- 针对性的维护有序性：
- 优先级队列（如最小堆或最大堆实现）可以直接聚焦于维护
k个有序的序列。例如，如果是一个最小堆实现的优先级队列，它自然地会将最小的元素放在堆顶。当插入新元素时，它可以根据元素的优先级（对于最小堆就是比较大小）快速地确定新元素是否属于这k个有序序列（比如新元素比堆顶元素小，就可以忽略它；如果比堆顶元素大，就可以替换堆顶元素并且调整堆结构来保持有序性）。- 高效的操作：
- 优先级队列的插入和删除操作在维护
k个有序序列的场景下时间复杂度相对较低。例如，基于堆实现的优先级队列，插入和删除操作的时间复杂度通常是（n是堆中的元素个数），而快排的平均时间复杂度是，并且快排是对整个数组进行操作，优先级队列可以只针对k个元素进行操作，所以在这种场景下优先级队列更加高效。
为什么用小顶堆？
- 大顶堆的问题：
- 定义大小为 k 的大顶堆，每次移动更新弹出最大元素，这样难以直接保留前 k 个高频元素，因为持续弹出最大元素会导致无法准确留存所需的前 k 个元素。
- 使用大顶堆时，若要按常规操作会对所有元素排序，难以做到仅排序 k 个元素来满足获取前 k 个高频元素的需求。
- 小顶堆的优势：
- 因为要统计最大前 k 个元素，小顶堆每次弹出最小元素，经过不断更新操作后，最终小顶堆里积累的就是前 k 个最大元素，能满足获取前 k 个高频元素的要求.
（引用：数据结构：大顶堆、小顶堆-CSDN博客）
优先级队列:
- 定义与概念
- 优先级队列（Priority Queue）是一种数据结构，它与普通队列不同的是，元素被赋予了优先级。当访问或删除元素时，具有最高（或最低，取决于具体实现）优先级的元素会首先被处理。它就像是一个排队系统，其中某些人（元素）可以因为更重要（更高优先级）而插队到前面。
- 存储结构与实现方式
- 基于数组或链表实现：可以通过数组或链表来存储元素，但这两种方式在插入和删除操作时效率可能较低。
- 基于堆实现（常见）：在实际应用中，优先级队列通常基于堆（Heap）数据结构来实现。堆是一种完全二叉树，分为最大堆和最小堆。在最大堆中，父节点的值大于或等于子节点的值；在最小堆中，父节点的值小于或等于子节点的值。通过这种结构，堆顶元素（根节点）就是优先级最高（最大堆为最大值，最小堆为最小值）的元素。
- 操作特点
- 插入（Push）操作：当向优先级队列中添加一个元素时，会根据元素的优先级将其放置在合适的位置。如果是基于堆实现的优先级队列，插入操作可能涉及到向上调整堆的操作，以维护堆的性质。
- 删除（Pop）操作：删除操作通常会移除优先级最高的元素（堆顶元素）。在基于堆的优先级队列中，删除后需要进行向下调整堆的操作，来保证堆的性质不变。
- 获取队首元素（Top）操作：可以获取优先级最高的元素，但不移除它。这在只需要查看最高优先级元素而不进行删除操作时很有用。
- 应用场景
- 任务调度：在操作系统中，任务可以有不同的优先级，优先级队列可以用来安排任务的执行顺序，确保高优先级的任务先被执行。
- 数据压缩算法：如哈夫曼编码，通过构建哈夫曼树（可以利用优先级队列来构建）来实现高效的数据压缩，其中频率较高（优先级高）的字符编码较短。
- 路径搜索算法：在一些路径搜索算法（如 A * 算法）中，使用优先级队列来存储待探索的节点，根据节点到目标的估计成本（优先级）来决定下一个探索的节点，有助于更高效地找到最优路径。
- 初始化：
对于基本数据类型，如int、double等，可以简单地指定元素类型来创建优先级队列，它会自动按照默认的比较规则（对于数值类型是从大到小，形成最大堆）初始化。
示例：priority_queue<int> pq;创建了一个存储整数的优先级队列pq，初始为空，默认是最大堆，即队首元素是当前队列中的最大值。- 指定容器和比较函数初始化（自定义比较规则）
class mycomparison { public: bool operator()(const int& lhs, const int& rhs) { return lhs > rhs; } };- 比较函数的作用和逻辑
当定义一个比较函数（例如
class mycomparison中的operator()函数）来构建最小堆时，返回lhs > rhs（其中lhs和rhs是比较的两个元素）是因为这个返回值的语义在优先级队列和堆的实现中是这样被解释的：
- 如果返回
true（即lhs > rhs），这意味着在堆的结构中，lhs应该被放置在比rhs“更靠下” 的位置。因为在最小堆中，我们希望较小的元素更靠近堆顶，所以当lhs大于rhs时，就认为lhs的优先级较低，应该在rhs的下方。- 例如，假设有两个节点
A和B，如果比较函数返回A > B，那么在构建最小堆的过程中，A会被放置在B的下方，以满足最小堆的性质，即较小的元素更靠近堆顶。在使用自定义比较函数来构建最大堆时，比较函数应该返回
lhs < rhs（假设lhs和rhs是比较的两个元素）来确定元素在堆中的排列顺序。
- 原因是，当返回
true（即lhs < rhs）时，在堆的结构中，lhs会被放置在比rhs“更靠下” 的位置。因为在最大堆中，我们希望较大的元素更靠近堆顶，所以当lhs小于rhs时，就认为lhs的优先级较低，应该在rhs的下方。- 例如，假设有两个节点
A和B，如果比较函数返回A < B，那么在构建最大堆的过程中，A会被放置在B的下方，以此来满足最大堆的性质，即较大的元素更靠近堆顶。
代码里 return lhs.second > rhs.second; 和 priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que; 需要额外思考一下。
class Solution {
public:
// 小顶堆
class mycomparison {
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second;//比较权重值即为频率，左大返回True
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
// 要统计元素出现频率
unordered_map<int, int> map; // map<nums[i],对应出现的次数>
for (int i = 0; i < nums.size(); i++) {
map[nums[i]]++;
}
// 对频率排序
// 定义一个小顶堆，大小为k
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
// 用固定大小为k的小顶堆，扫描所有频率的数值
for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
pri_que.push(*it);
if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
pri_que.pop();
}
}
// 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
vector<int> result(k);
for (int i = k - 1; i >= 0; i--) {
result[i] = pri_que.top().first;
pri_que.pop();
}
return result;
}
};总结：
标签：第十一天,优先级,队列,rhs,元素,随想录,que,求值,lhs From： https://blog.csdn.net/qq_53853175/article/details/143674852主要是了解了栈，双端队列，优先队列的使用，其中 347.在理解上稍微麻烦一些。
面试题：栈里面的元素在内存中是连续分布的么？
这个问题有两个陷阱：
- 陷阱1：栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中不一定是连续分布的。
- 陷阱2：缺省情况下，默认底层容器是deque，那么deque在内存中的数据分布是什么样的呢？ 答案是：不连续的，下文也会提到deque。
递归的实现是栈：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。