150. 逆波兰表达式求值
本题不难，但第一次做的话，会很难想到，所以先看视频，了解思路再去做题
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<long long> st;
for (const string& token : tokens) {
if (token == "+" || token == "-" ||token == "*" || token == "/") {
long long num1 = st.top();
st.pop();
long long num2 = st.top();
st.pop();
if (token == "+") st.push(num2 + num1);
if (token == "-") st.push(num2 - num1);
if (token == "*") st.push(num2 * num1);
if (token == "/") st.push(num2 / num1);
}
else {
st.push(stoll(token)); // 将字符串转换为 long long
}
}
int result = st.top();
return result;
}
};最开始以为和那个括号匹配本质一样的，仔细一看很多字符串怎么解决？以为是char，再仔细看是包含字符串的数组。所以要用到
stoll 是一个标准库函数，用于将字符串转换为 long long 类型。stoll 的全称是 "string to long long"，它的原型定义在 <string> 头文件中。st.push(stoll(token)); 是用来将 token（字符串）转换为一个 long long 数字，并将其压入栈中。整体不难，但是一些东西还是要注意些。
for (const string& token : tokens)const：表示 token 是一个常量引用，无法在循环体内修改 token 的值。这可以防止不必要的修改，并表明你的意图是只读操作。string&：表示 token 是对 tokens 容器中每个元素的引用，而不是拷贝。如果不使用引用，则每次循环都会复制一个字符串对象，可能会带来额外的性能开销。使用引用避免了这种不必要的拷贝操作。
这样可以处理逆波兰表达式中的数字部分
题目链接/文章讲解/视频讲解：代码随想录
239. 滑动窗口最大值 （有点难度，可能代码写不出来，但一刷至少需要理解思路）
之前讲的都是栈的应用，这次该是队列的应用了。其实这题思路核心还是存储几个可能是大的，一个为k的栈，导入，当导入一个，就把前面比它小的全弹出来，此时还得把再把最前面的给弹出（有可能在前面压入的时候，已经弹出了，弹出了就不管了。）
本题算比较有难度的，需要自己去构造单调队列，建议先看视频来理解。
弹出，就是把滑动窗口是要弹出的给弹出（前提是之前就弹出了）
压入，就是比较下栈内的各个元素，比自己小的，没可能成为最大的，直接淘汰。
感觉就是打比赛，一代更有一代强。除了最开始几个，老的人过了k年会死去，新人会登场上场就把垃圾的打死淘汰掉，场上只有强者生存。
题目链接/文章讲解/视频讲解：代码随想录
class Solution {
private:
class MyQueue {
public:
deque<int> que;
void pop(int value) {
if (!que.empty() && value == que.front()) {
que.pop_front();
}
}
void push(int value) {
while (!que.empty() && value > que.back()) {
que.pop_back();
}
que.push_back(value);
}
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;
}
};347.前 K 个高频元素 （有点难度，可能代码写不出来，一刷至少需要理解思路）
大/小顶堆的应用， 在C++中就是优先级队列
本题是 大数据中取前k值 的经典思路，了解想法之后，不算难。
题目链接/文章讲解/视频讲解：代码随想录
本质上就是上图，首先要构建一个map，用来存储他们的次数，然后把它们一个个扔进竞技场。垃圾的就扔了。思路还是比较简单的，但是具体实现还是比较复杂的。
一些语法还是要学一学，priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;这句代码中priority_queue 是一个模板类，用于实现优先队列。默认情况下，它是一个最大堆，意味着队列中最大的元素具有最高优先级。为了实现自定义优先级规则（如最小堆或其他复杂排序），可以提供自定义的比较器。
pair<int, int>，表示优先队列中存储的是整型对 (std::pair<int, int>)。
vector<pair<int, int>>，这是 priority_queue 的底层容器，通常使用 std::vector。
mycomparison，这是一个自定义的比较器，用来定义优先队列中元素的优先级顺序。这里是代码中通过重载 operator() 来定义比较规则。在这个例子中，优先队列按 pair 的第二个元素进行升序排序（即 lhs.first > rhs.first），从而实现最小堆。当你插入 pair<int, int> 元素时，优先队列会根据你定义的规则对它们进行排序。在这个例子中，最小的 pair<int, int> 对会首先被弹出。
class Solution {
public:
class myComparison{
public:
bool operator()(const pair<int ,int>&lhs,const pair<int ,int>&rhs){
return lhs.second>rhs.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> map;
for (int num:nums) {
map[num]++;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, myComparison> pri_que;
// 用固定大小为k的小顶堆，扫面所有频率的数值
for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
pri_que.push(*it);
if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
pri_que.pop();
}
}
vector<int>result(k);
for(int i=k-1;i>=0;i--)
{result[i]=pri_que.top().first;
pri_que.pop();
}
return result;
}
};