逆波兰表达式
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式，如
( 1 + 2 ) * ( 3 + 4 )。 - 该算式的逆波兰表达式写法为
( ( 1 2 + ) ( 3 4 + ) * )。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成
1 2 + 3 4 + *也可以依据次序计算出正确结果。 - 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
这里其实与二叉树的后序遍历（左右中）是差不多的。
在这里我们可以直接使用栈来解决，思路就是将数字入栈，然后遇到操作符，弹出两个数字进行运算，再将结果入栈。
图示如下1：
int f (int a, int b, string op) {
if (op == "+") return a + b;
if (op == "-") return a - b;
if (op == "*") return a * b;
if (op == "/") return a / b;
return 0;
}
int evalRPN(vector<string>& tokens) {
stack<int> stk;
for (int i = 0; i <= tokens.size() - 1; i++){
// 当遇到操作符的时候
if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
// 注意栈的弹出顺序，先弹出b再弹出a
int b = stk.top();
stk.pop();
int a = stk.top();
stk.pop();
stk.push(f(a, b, tokens[i]));
}
else {
stk.push(stoi(tokens[i])); // 这里要注意将字符串转为整数
}
}
int ans = stk.top();
stk.pop();
return ans;
}唯一要注意的就是弹出元素的顺序，先弹出的是第二个操作数，之后才是第一个。
滑动窗口最大值
暴力求解
最直观的解法是使用 max_element() 直接返回每次滑动窗口的最大值，然而这种方法会超时，时间复杂度为 ，k 是窗口大小，遍历数组 n - k + 1 次，max_element() 遍历k次。
vector<int> maxSlidingWindow(vector<int>& nums, int k) { // 暴力求解超时
vector<int> ans;
for (int i = 0; i + k <= nums.size(); i++) {
ans.push_back(*max_element(nums.begin() + i, nums.begin() + i + k));
}
return ans;
}单调队列2
这里我们可以使用单调队列来解决，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。
我们需要的队列有以下操作：
class MyQueue {
public:
void pop(int value) {
}
void push(int value) {
}
int front() {
return que.front();
}
};在每次移动滑动窗口的时候，调用 pop() 和 push() 方法，然后 front() 方法返回队列的最大值。
这里有个思路是：没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。
以下图示展示了单调队列的过程：
设计单调队列的时候，pop，和 push 操作要保持如下规则：
pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
在保持以上规则的前提下，每次滑动窗口移动时，我们只需要调用 front() 方法就可以得到窗口的最大值。
下面是一个更清晰展示单调队列的过程：
那么使用哪种队列呢，答案是 deque，因为 deque 可以在队列的两端进行插入和删除操作。
那么根据以上规则，我们可以实现 MyQueue 类：
class MyQueue {
public:
deque<int> que;
// 每次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);
}
int front() {
return que.front();
}
};然后就是遍历数组，实现求解滑动窗口的最大值：
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MyQueue que;
vector<int> ans;
for (int i = 0; i < k; i++) { // 先把前k个元素push进队列
que.push(nums[i]);
}
ans.push_back(que.front()); // 记录前k个元素的最大值
for (int i = k; i < nums.size(); i++) {
que.pop(nums[i - k]); // 滑动窗口移除最前面元素
que.push(nums[i]); // 滑动窗口前加入最后面的元素
ans.push_back(que.front()); // 记录对应的最大值
}
return ans;
}前k个高频元素
这里我们可以先用一个哈希表来统计每个元素出现的频率，然后再使用优先级队列来维护前 k 个高频元素。
优先级队列（priority_queue）底层通常基于堆实现，能在 O(log n) 的时间复杂度内插入或取出优先级最高的元素。默认情况下是大顶堆，即每次取出的都是值最大的元素。
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
map[nums[i]]++;
}
// 优先队列，大顶堆
priority_queue<pair<int, int>> pq;
for (auto it = map.begin(); it != map.end(); it++) { // 遍历map，将map中的元素push进优先队列
pq.push(make_pair(it->second, it->first)); // 优先队列中存储的是pair<int, int>，第一个元素是频率，第二个元素是元素值
}
vector<int> ans;
for (int i = 0; i < k; i++) { // 取出前k个元素
ans.push_back(pq.top().second);
pq.pop();
}
return ans;
}要注意的是，优先队列默认是大顶堆，所以我们要将频率作为第一个元素，元素值作为第二个元素，这样就可以取出前 k 个高频元素。
总结
今天的这个单调队列还是有点难以理解，不过难的并不是 myQueue 类的实现，在下面的遍历逻辑里，饶了半天有点没绕明白。
最后要知道什么时候用优先级队列，什么时候用单调队列
- 优先级队列：求最大值或最小值
- 单调队列：求最大值或最小值，同时还要保持队列里的元素是单调的