逆波兰表达式

思路

用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

这里记录string类型相关操作：

1. 判断token是否是数字，不可像char类型用string重载的>=,<=，前者由于用ASCII码表示，后者按字典序比较，例如1<2所以字符串比较 "10" < "2"。

2. 所以直接判断token是否是运算符，else是数字。而string转数字的函数有stoi,stof,sotll。

代码

直接粘贴的代码随想录就不写了

滑动窗口最大值

思路

一开始想到用栈或队列维护最大值。因为滑动窗口是先进先出，栈不好用。队列虽满足特性但不能无脑入队，首先规定队首是当前窗口最大值，队首出队后的队首要是下个窗口的最大值，那么每次入队就应该保证队列里没有比自己小的元素，队首不能动只能从队尾出，想到双端队列。

总结：实现一个单调队列——具体而言递减的双端队列。

之后就是实现细节——1.队首何时出队2.何时记录最大值。

这里用L和R双指针模拟窗口，即初始化L=1-k，R=0.

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> dq;//dq维持递减
        //L从1-k到1-n,R从0到n-1
        for(int L=1-k,R=0;R<nums.size();R++,L++){
            //L>0时若剔除窗口的首元素=dq首元素
            if(L>0 && nums[L-1] == dq.front()){
                dq.pop_front();
            }
            //dq中小于nums[R]的移除——保持递减
            while(!dq.empty() && nums[R]>dq.back()){
                dq.pop_back();
            }
            dq.emplace_back(nums[R]);
            //L>=0时记录最大值
            if(L>=0){
                ans.emplace_back(dq.front());
            }
        }
        return ans;
    }
};