代码随想录算法训练营第十一天| 150. 逆波兰表达式求值,239. 滑动窗口最大值

参考文档：代码随想录
阅读大概需要5min

150. 逆波兰表达式求值

力扣题目链接(opens new window)

根据 逆波兰表示法，求表达式的值。

有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

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

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

输入: [“10”, “6”, “9”, “3”, “+”, “-11”, " * ", “/”, " * ", “17”, “+”, “5”, “+”]

输出: 22

解释:该算式转化为常见的中缀算术表达式为：

第一次写遇到的问题

1. 输入后缀表达式输出中缀表达式原理是什么？

   • 初始化一个栈：用于存储操作数。

   • 遍历输入的后缀表达式（以字符串数组形式）

     ：

     • 如果遇到的是数字，则将其转换成整数或浮点数并压入栈中。
     • 如果遇到的是运算符，则从栈中弹出两个顶部元素（最近压入的两个数字），用该运算符对这两个数字进行运算，并将结果压回栈中。

   • 最终结果：当所有输入都被处理后，栈顶元素即为计算结果。

2. 是先进栈的除后进栈的，还是后进栈的除先进栈的？

   • 是先进栈的乘后进栈的，就是后出栈的除以先出栈的，比如这里是13/5.
   • 

3. 怎么实现返回以及怎么实现？

代码实现如下：

class Solution {
public:
    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]));
            }

            
        }
        long long result = st.top();
            
    }
};

看完代码后的问题

1. 这里的stoll(tokens[i]) 中的stoll是什么？

stoll 是 C++ 标准库中的一个函数，全称为 “string to long long”。它用于将字符串转换为 long long 类型的整数。

239. 滑动窗口最大值

力扣题目链接(opens new window)

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

进阶：

你能在线性时间复杂度内解决此题吗？

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

第一次写的想法

1. 暴力解法每次找到一个最大值保存，然后遍历保存的找到最大值？
   • 暴力解法显然是不对的，时间复杂度为O(n * k);
2. 找到一个当最大值，然后再计算。
   • 和暴力解法一样，这里的当时相的是把每个窗口的最大值找出来保存起来，再做，显然也是需要不停的遍历保存，也是复杂度O(n * k);
3. 用什么容器来做？
   • 单调队列，即单调递减或单调递增的队列

题目解析

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;
    }
};

看完解析的几个问题

1. 单调队列是怎么维护序列的，就是怎么维护大小，以及判断那个该出去，哪个该保留？
   • 递增单调队列：如果新元素比队尾元素小，则不断移除队尾元素，直到队尾元素不再大于新元素为止。
   • 移除过期元素，检查队首元素是否还在当前窗口范围内，如果不在，则将其移除。
2. 队列不是只先进先出吗？为什么单调队列可以移除队尾元素？
   • 单调队列并不是一个标准的FIFO队列，而是一种特殊的双端队列（Deque, Double-ended Queue），它允许从两端进行插入和删除操作。

这里是每天回答3个问题
今日用时1h31min
如果对你有帮助的话，麻烦点一个免费的赞👍