【算法day10】栈与队列：拓展与应用

题目引用

---

1. 逆波兰表达式求值
2. 滑动窗口最大值
3. 前k个高频元素

1.逆波兰表达式求值

---

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = [“2”,“1”,“+”,“3”,“*”]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = [“4”,“13”,“5”,“/”,“+”]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = [“10”,“6”,“9”,“3”,“+”,“-11”,““,”/“,””,“17”,“+”,“5”,“+”]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

这道题目就很简单，我们只需要定义一个栈st，然后遍历一遍数组，不是符号的话就入栈，遇到符号的话就从栈中取出两个元素进行加减乘除运算，再压入栈中。最后返回栈中元素。

来看代码：

int evalRPN(vector<string>& tokens) {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;}

这里需要注意栈中元素进行运算时可能会溢出，所以使用long long来定义中间值。

2.滑动窗口最大值

---

给你一个整数数组 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

示例 2：

输入：nums = [1], k = 1
输出：[1]

这道题比较难实现，如果是第一次刷题的话遇到这种题目就可以直接跳过了。
我们来看题目，题目要求我们找到每次滑动窗口滑动时的最大值，那么我们就可以想一下，可不可以创建一个自动找到最大值或者说第二大的数据结构呢，可能很多人会想到优先级队列。优先级队列是一种思路，可是我们再仔细想想，我们一开始就要入一些元素进来，而只有优先级队列的top()是我们需要的，其他的我们都可以丢弃，那这就造成了空间的浪费，而且随着滑动窗口向后移动，遇到比原来top()小，比其他值大的数时就可能产生混乱，无法判断这个值什么时候该弹出，或者早该弹出却因为其他值比它大而没有弹出导致后续的结果出现问题。
所以我们需要一种方便我们进行弹入弹出又能便于维护的数据结构，是什么呢？没有~
但是我们可以造一个，而底层我们就用deque这种便于头插头删尾插尾删的数据结构。当我们滑动窗口向前滑动时，我们要把即将进入的值与已经在队列中的值一一比对，只要比即将要插入的值小，那么就直接pop_back()，直到找到比自己大的数或者队列清空。同时队列头部与将要滑出窗口的值进行比较，如果等于就大胆pop_front()，然后再将尾插头删后的队列的front()插入结果数组中,如此循环，就得到了每一轮的最大值。
这样说大概大家还是云里雾里，那么来看代码吧：

	class Myqueue{private:deque<int> que;public:void push(int x){while(!que.empty()&&x>que.back()) que.pop_back();que.push_back(x);}void pop(int x){if(!que.empty()&&x==que.front()) que.pop_front();}int front(){return que.front();}};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;}

3.前k个高频元素

---

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

这题相较于上一题来说就稍微简单一点了，我们直接说思路吧，他要找前k频率的元素，那么我们就要先使用unordered_map将每个元素出现的频率统计一下，然后再用小根堆来记录，为什么是小根堆，因为是前k高频率，使用小根堆的话，当堆中元素大于k个时就可以直接将出现频率最小的弹出堆中，便于维护更新。
最后将堆中元素倒序输出即可

struct compare{bool operator()(const pair<int,int> lhs,const pair<int,int> rhs){return lhs.second>rhs.second;}};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>,vector<pair<int,int>>,compare> que;for(unordered_map<int,int>::iterator it=map.begin();it!=map.end();it++){que.push(*it);if(que.size()>k){que.pop();}}vector<int> res(k);for(int i=k-1;i>=0;i--){res[i]=que.top().first;que.pop();          }return res;}

总结

今天的题目普遍比较难，大家下去一定要自己敲一下感受感受。