训练营第十一天 | 150. 逆波兰表达式求值

 150. 逆波兰表达式求值

做题思路

遇到操作符，出栈，从栈口取出俩元素；遇到数字，入栈

栈的应用场景：相邻元素的消除

逆波兰表达式：即后缀表达式

来自二叉树的后序遍历：左右中

代码细节

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        // 栈：存储数字
        stack<long long> nums;
        for (int i =0; i < tokens.size(); i++)
        {
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
            {
                // 遇到操作符，出栈，取出俩元素
                long long num1 = nums.top();
                nums.pop();
                long long num2 = nums.top();
                nums.pop();
				// 注意：num2和num1的顺序
                if(tokens[i] == "+") nums.push(num2 + num1);
                if(tokens[i] == "-") nums.push(num2 - num1);
                if(tokens[i] == "*") nums.push(num2 * num1);
                if(tokens[i] == "/") nums.push(num2 / num1);
            } else {
                // 遇到数字，入栈。stoi将字符串类型转换为整型
                nums.push(stoll(tokens[i]));
            }
        }

        // 取出栈顶元素，即最后一个入栈的元素
        int res = nums.top();
        nums.pop();
        return res;
    }
};

 239. 滑动窗口最大值

（有点难度，可能代码写不出来，但一刷至少需要理解思路）

单调队列正式登场！| LeetCode：239. 滑动窗口最大值_哔哩哔哩_bilibili

 347.前 K 个高频元素 

（有点难度，可能代码写不出来，一刷至少需要理解思路）

优先级队列正式登场！大顶堆、小顶堆该怎么用？| LeetCode：347.前 K 个高频元素_哔哩哔哩_bilibili

栈与队列总结

代码随想录