复习Day16：栈与队列part03：150.逆波兰表达式求值、239.滑动窗口最大值、260. 只出现一次的数字III

往期链接：https://blog.csdn.net/weixin_43303286/article/details/131869968?spm=1001.2014.3001.5501

https://blog.csdn.net/weixin_43303286/article/details/131906418?spm=1001.2014.3001.5501

150. 逆波兰表达式求值

没什么好说的，用栈维护，取栈顶两个元素运算后再入栈。注意数据类型用long long。以及减法和除法有顺序。

239. 滑动窗口最大值

本题使用单调队列，难度是hard。

单调队列的讲解我选择看代码随想录的，Labuladong的使用双链表作为单调队列的底层实现感觉有点不好理解，卡哥用的是直接用双头队列deque。

链接：

为了实现这道题，我们需要这样一个队列：这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。

这个队列应该长这样：

1

class MyQueue {
public:
    void pop(int value) {
    }
    void push(int value) {
    }
    int front() {//最大值
        return que.front();
    }
};
1
2
3
4
5
6
7
8
9
10

260. 只出现一次的数字III

给你一个整数数组 nums，其中恰好有两个元素只出现一次，
其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。


1
2
3
4

这题使用位运算，代码：

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        long res = 0;
        for(int num : nums){
            res ^= num;
        }
        int bit = res & -res;
        int a = 0, b = 0;
    for (int num : nums) {
        if (num & bit) {
            a ^= num;
        } else {
            b ^= num;
        }
    }
    
    return {a, b};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20