逆波兰表达式求值+滑动窗口最大值

逆波兰力扣链接
滑动窗口力扣链接

逆波兰思路

遇到数字入栈，遇到操作符出栈两个数字x1,x2计算,计算完返回结果入栈；

滑动窗口最大值思路

已知：

1. 给出数组vector &nums;和窗口大小k
2. 要求返回每次移动的最大值

使用单调队列解决——Myqueue;
myqueue底层数据结构是双端队列(deque que)，c++没用直接实现，需要我们自己实现pop(int value)和push(int value);
其中：

1. pop(int value)遵循以下逻辑：只有当队列不为空最大值也就是que.front() == value的时候才进行que.pop_front();
2. push(int value)遵循以下逻辑：当push的数值大于队尾元素的时候，把所有队尾小于它的元素都弹出，因为一旦有更大的值进来，较小的值就不可能成为最大的值（更老还更小，会在有机会成为最大前被pop掉）
3. int front():还实现一个front(),return que.front();

具体代码

逆波兰：

```cpp
class Solution {
public:int changeINT(string s){int len = s.size();int result = 0;if(s[0] == '-'){for(int i = 1; i < len;i++){result*=10;result-=(s[i]-'0');}}else{for(int i = 0; i < len;i++){result*=10;result+=(s[i]-'0');}}return result;}int evalRPN(vector<string>& tokens) {stack<int> st;for(auto token:tokens){if(token != "+"&& token!="-"&&token!="*"&&token!="/"){int x = changeINT(token);st.push(x);}else if(token == "+"){int x1 = st.top();st.pop();int x2 = st.top();st.pop();x2+=x1;st.push(x2);}else if(token == "-"){int x1 = st.top();st.pop();int x2 = st.top();st.pop();x2-=x1;st.push(x2);}else if(token == "*"){int x1 = st.top();st.pop();int x2 = st.top();st.pop();x2*=x1;st.push(x2);}else if(token == "/"){int x1 = st.top();st.pop();int x2 = st.top();st.pop();x2/=x1;st.push(x2);}}int result = st.top();return result;}
};

滑动窗口最大值：
```cpp
```plaintext
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;}
};