150. 逆波兰表达式求值

思路： 如果遇到符号，取出栈顶的两个数计算，并把结果存入栈；遇到数字存入栈中；栈最后一个元素就是最终结果。
注意点： 用栈解题；stoll函数将字符串类型的参数转换为long long int类型的值返回，解析str并将其内容解释为指定基数的整数

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> result;int num1=0, num2=0, ret=0;for(int i=0;i<tokens.size();i++){//如果遇到符号 取出栈顶的两个数计算 并把结果存入栈if(tokens[i]=="+" || tokens[i]=="-" || tokens[i]=="*" || tokens[i]=="/"){num1=result.top();result.pop();num2=result.top();result.pop();if(tokens[i]=="+") ret = num2+num1;if(tokens[i]=="-") ret = num2-num1;if(tokens[i]=="*") ret = num2*num1;if(tokens[i]=="/") ret = num2/num1;result.push(ret);}//遇到数字存入栈中 tokens是string类型 需要类型转化else  result.push(stoll(tokens[i]));}//栈最后一个元素就是最终结果return result.top();}
};

239. 滑动窗口最大值

思路： 实现一个单调队列找出窗口的最大值，
注意点：

• 单调队列就是滑动窗口，找出最大值，并且需要把不符要求的值弹出来，更新滑动窗口的内容，维护最大值。
• 需要把第一个滑动窗口的内容先存入队列中，找到第一个最大值。
• 重点学习单调队列，往后根据场景，实现单调递增/递减的队列。

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> result;Myque que;for(int i=0;i<k;i++){que.push(nums[i]);}result.push_back(que.front());for(int i=k;i<nums.size();i++){que.pop(nums[i-k]);que.push(nums[i]);result.push_back(que.front());}return result;}
private://创建私有成员类 单调递减队列
class Myque
{
public:deque<int> que;//弹出窗口前面的元素void pop(int value){if(!que.empty() && que.front()==value) que.pop_front();}void push(int value){//容器不为空 比较大小 尾部元素小则弹出，再存入当前较大值while(!que.empty() && que.back()<value) que.pop_back();que.push_back(value);}int front(){return que.front();}
};
};

347.前 K 个高频元素

思路： 优先级队列实现小顶堆，小顶堆按照元素出现频率从小到大对元素排序，小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。
注意点：

• 优先级队列，本质是堆；对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式；内部元素是自动依照元素的权值排列。
• 缺省情况下priority_queue利用max-heap完成按照元素频率对元素的排序，这个顶堆是以vector为表现形式的complete binary tree（完全二叉树）。
• 堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。
• 如果父亲结点是大于等于左右孩子就是大顶堆，堆头是最大元素，元素权值从大到小排序；父亲结点小于等于左右孩子就是小顶堆，堆头是最小元素，元素权值从小到大排就排序。

class Solution {
public://小顶堆class mycomparison{public:bool operator()(const pair<int,int>& lhs, const pair<int, int>& rhs){//lhs rhs是对组 要求对频率排序 频率对应map的valuereturn lhs.second>rhs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {//1.按照频率对元素排序 对频率统计使用mapunordered_map<int, int> map;for(int i=0;i<nums.size();i++){map[nums[i]]++;//元素是key 频率是value}//2.定义小顶堆 小顶堆按照元素频率对元素从小到大排序priority_queue<pair<int,int>, vector<pair<int, int>>, mycomparison> pri_que;//3.小顶堆扫描所有元素for(unordered_map<int, int>::iterator it=map.begin();it!=map.end();it++){pri_que.push(*it);//底层是vector 使用push存数据 按照mycomparison排序if(pri_que.size()>k) pri_que.pop();//保证小顶堆的大小为k}//4.顶堆倒序存入数组 找出前k个高频元素vector<int> result(k);//数组大小为kfor(int i=k-1;i>=0;i--)//倒序存放{result[i]=pri_que.top().first;//pri_que.top()是对组 .first是元素 .second是元素频率pri_que.pop();}return result;}
};

总结

一、五个问题
一问：C++中stack，queue 是容器么？
答：容器适配器，一种数据结构

二问：我们使用的stack，queue是属于那个版本的STL？
答：SGI STL版本

三问：我们使用的STL中stack，queue是如何实现的？
答：SGI STL版本下，默认是以缺省情况下deque作为底层实现的，也可以指定其他容器来作为底层实现，例如vector、list

四问：stack，queue 提供迭代器来遍历空间么？
答：stack、queue是容器适配器，不提供迭代器遍历空间。但是stack、queue在SGI STL版本下通常使用缺省情况下deque（默认）或者vector或者list作为底层实现的容器，可以使用这些容器

五问：栈里面的元素在内存中是连续分布的么？
答：不是，根据底层实现的容器不同，栈的元素在内存分布也不同。例如，deque实现的栈的元素在内存是不连续分布的，但是vector实现的栈的元素在内存是连续分布的。

二、两个陷阱
陷阱1：栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中是不是连续分布。
陷阱2：缺省情况下，默认底层容器是deque，那么deque的在内存中的数据分布是不连续的，回顾这个学习笔记提到的deque内部结构。

三、两个学习重点
重点1：单调队列，设计时保证队列里单调递减或递增的原则；场景不同，队列的对外接口功能也不同。题239只是其中一个例子
重点2：优先级队列，内部元素是自动依照元素的权值排列，本质是堆；对外接口只有从队头取元素，从队尾添加元素
重点3：堆，是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。题347通过优先级队列实现小顶堆找出前k个高频元素，注意为什么不用大顶堆。