根据代码随想录，记录学习一些算法经验
1.栈与队列的理论基础
队列是先进先出，栈是先进后出。栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。
栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。
STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。
栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。
如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构。
队列中先进先出的数据结构，同样不允许有遍历行为，不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。
所以STL 队列也不被归类为容器，而被归类为container adapter（ 容器适配器）。
2.用栈实现队列（232题）
题目描述：
使用栈实现队列的下列操作：
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。
模拟题：使用两个栈来模拟即可实现，一个栈是输入栈，另一个是输出栈，注意弹出队列元素时候，要注意首先看输出栈是否为空，在看输入栈是否为非空，不为空全部压入栈中在弹出。
class MyQueue {
public:
stack<int>stIn;//输入栈
stack<int>stOut;//输出栈
MyQueue() {
}
void push(int x) {//压入队列，其实就是输入栈进栈
stIn.push(x);
}
int pop() {//弹出队列
if(stOut.empty()){//输出栈为空
while(!stIn.empty()){//输入栈不为空
stOut.push(stIn.top());//把全部输入栈压入到输出栈中
stIn.pop();//弹出输出栈的元素
}
}
int result = stOut.top();//结果就是输出栈弹出的元素
stOut.pop();//弹出元素
return result;
}
int peek() {//队头元素
int res = this->pop();//复用了Pop函数
stOut.push(res);
return res;
}
bool empty() {//判断是否为空，两个栈都空即为空
return stIn.empty() && stOut.empty();
}
};- 时间复杂度: push和empty为O(1), pop和peek为O(n)
- 空间复杂度: O(n)
3.用队列实现栈（225题）
题目描述：
使用队列实现栈的下列操作：
- push(x) -- 元素 x 入栈
- pop() -- 移除栈顶元素
- top() -- 获取栈顶元素
- empty() -- 返回栈是否为空
使用两个队列做法：一个队列实际操作，另一个队列进行辅助，下面实现代码：
class MyStack {
public:
queue<int>que1;//两个队列实现，队列2实现辅助 功能
queue<int>que2;//
MyStack() {
}
void push(int x) {
que1.push(x);//队列的压入就是相当于压栈
}
int pop() {//弹出元素
int size = que1.size();//计算队列的大小
size--;//先做一个减一操作留一个元素
while(size--){//将队列1转队列2中，队列1的头的元素压入队列2，再弹出
que2.push(que1.front());
que1.pop();
}
int result = que1.front();//队列1剩下的元素就是要弹出的元素
que1.pop();//弹出
que1 = que2;//队列2赋值给队列1
while(!que2.empty()){//清空队列2
que2.pop();
}
return result;//返回值
}
int top() {//队列尾就是栈头元素
return que1.back();
}
bool empty() {//队列1空了栈空
return que1.empty();
}
};队列2也就是在弹出元素作为辅助作用，
- 时间复杂度: pop为O(n)，其他为O(1)
- 空间复杂度: O(n)
下面用一个队列实现的：一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。
class MyStack {
public:
queue<int>que1;//1个队列实现
MyStack() {
}
void push(int x) {
que1.push(x);//队列的压入就是相当于压栈
}
int pop() {//弹出元素
int size = que1.size();//计算队列的大小
size--;//先做一个减一操作留一个元素
while(size--){//将队列1的头的元素压入队列1尾，再弹出
que1.push(que1.front());
que1.pop();
}
int result = que1.front();//队列1剩下的元素就是要弹出的元素
que1.pop();//弹出
return result;//返回值
}
int top() {//队列尾就是栈头元素
return que1.back();
}
bool empty() {//队列1空了栈空
return que1.empty();
}
};- 时间复杂度: pop为O(n)，其他为O(1)
- 空间复杂度: O(n)
4.有效的括号 （20题）
题目描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
示例 1:
- 输入: "()"
- 输出: true
使用栈来解法：括号匹配是典型栈解法应用，栈一般用来做对称匹配题目，需要注意字符串不匹配的情况，三种情况：左括号多余，括号不匹配，右括号多余，技巧：匹配左括号，右括号进栈，最后对比是否相等就可以，遇左进栈，遇右弹出比较。
class Solution {
public:
bool isValid(string s) {
stack<int>st;//申请一个栈
for(int i = 0;i < s.size(); i++){//遍历整个字符串
if(s[i] == '('){//遇到左括号全部把右括号压入栈
st.push(')');
}else if(s[i] == '{'){
st.push('}');
}else if(s[i] == '['){
st.push(']');
}else if(st.empty() || s[i] != st.top()){//判断右括号多余和括号不匹配的情况
return false;
}else{//相等弹出括号
st.pop();
}
}
return st.empty();//如果全部匹配，返回正确，否则是左括号多余情况，返回错误
}
};- 时间复杂度: O(n)
- 空间复杂度: O(n)
5.删除字符串中的所有相邻重复项 （1047题）
题目描述：给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
- 输入："abbaca"
- 输出："ca"
- 解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
思路：删除相邻重复项，其实就是删除对称项的问题，首先需要考虑栈能否解决，这道题首先考虑好栈如何解决的，在定义一个字符串去接收，然后要注意字符串的顺序问题，栈存放遍历过的元素，
class Solution {
public:
void reverse(string& s,int start, int end){//自己定义的反转函数
for(int i = start,j = end;i < j;i++,j--){
swap(s[i],s[j]);
}
}
string removeDuplicates(string s) {//删除字符串所有相邻重复项
stack<int>st;//定义一个栈，一般来做对称匹配问题很好用
for(char c : s){//遍历每个字符串的字符
if(st.empty() || c != st.top()){//如果为空或者下一个字符不等于栈顶元素压入栈中
st.push(c);
}else{//就是栈顶元素相等就是遇到重复元素，已经消除了一对对称的元素
st.pop();
}
}
string t = "";//定义一个字符串去接收
while(!st.empty()){//将栈里的元素加入到字符串里
t += st.top();
st.pop();
}
reverse(t,0,t.size()-1);//因为加入字符串的顺序不对需要反转一次
return t;
}
};递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，
- 时间复杂度: O(n)
- 空间复杂度: O(n)
6.逆波兰表达式求值（150题）
题目描述：
根据 逆波兰表示法，求表达式的值。
有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
- 输入: ["2", "1", "+", "3", " * "]
- 输出: 9
- 解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
其实相当于二叉树的后序遍历，运算符是中间节点，就是二叉树的后序遍历，这种运算有相邻字符串消除模式，想到栈的解法，
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st; //定义一个栈
for (int i = 0; i < tokens.size(); i++) {//从字符串遍历
if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {//遇到了运算符进行运算
int num1 = st.top();//定义一个数去接收
st.pop();//然后从栈弹出
int 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(stoi(tokens[i]));//stoi函数将字符串转换成整形，压入栈中
}
}
int result = st.top();//结果就是最后栈顶元素
st.pop(); //弹出
return result;
}
};- 时间复杂度: O(n)
- 空间复杂度: O(n)
7.滑动窗口最大值 （239题）
题目描述：
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
思路：首先优先级队列为何不行，因为如果排序了打乱了原来顺序，错误，所以我们采用自定义的单调队列来实现，要一个压入函数，和一个弹出函数，且告知队头元素就是我们需要的最大值我们的诉求，弹出元素：如果窗口移除元素等于单调队列出口元素，弹出元素，否则不操作，Push函数，如果元素大于入口元素，则将队列入口元素弹出，改变的其实是前面的值，不改变后面的局部最大保存下来，后面就是遍历操作即可。
class Solution {
private:
class MyQueue{//自己实现的单调队列，其实就是维护一个所需的最大值而已
public:
deque<int>que;//使用deque实现单调队列，双端队列
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());//得到一个结果
for(int i = k;i<nums.size();i++){//再将后面元素操作
que.pop(nums[i - k]);//移除最前面的元素
que.push(nums[i]);//压入最后的元素
result.push_back(que.front());//记录对应最大值
}
return result;
}
};- 时间复杂度: O(n)
- 空间复杂度: O(k)
8.前 K 个高频元素（347题）
题目描述：
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
- 输入: nums = [1,1,1,2,2,3], k = 2
- 输出: [1,2]
思路： 统计元素出现频率，对频率排序，找出前k个频率的元素，
使用数据结构map，排序使用优先级队列，
priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。
堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。大顶堆（堆头是最大元素），小顶堆（堆头是最小元素）。
如果使用大根堆返回最小前K个元素
我们要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。
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;//定义一个哈希表map
for (int i = 0; i < nums.size(); i++) {//对数组的每个元素进行记录个数
map[nums[i]]++;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison>
pri_que;//定义一个优先级队列小根堆排序方式
//将哈希表遍历
for (unordered_map<int, int>::iterator it = map.begin();
it != map.end(); it++) {
pri_que.push(*it);//将哈希值插入压入队列
//固定大小为k，超过了弹出小元素
if (pri_que.size() > k) {
pri_que.pop();
}
}
vector<int> result(k);//定义结果数据
//因为结果需要知道前k高的元素，所以需要倒序插入到数组中
for (int i = k - 1; i >= 0; i--) {
result[i] = pri_que.top().first;//插入下标
pri_que.pop();//弹出队列
}
return result;
}
};- 时间复杂度: O(nlogk)
- 空间复杂度: O(n)
总结：
栈与队列的理论基础：栈先进后出，队列先进先出，无迭代器，底层可以是数组链表队列，都叫容器适配器
用栈实现队列：模拟一下即可，使用两个栈，一个输出栈，一个输入栈，栈与队列不能空操作，其实就需要想明白弹出操作即可，先把输出栈清空，再把输入栈全部压入，弹出
用队列实现栈：也是模拟题，用两个队列实现，一个队列操作，另一个作为辅助队列，其实也是想明白栈的形式原理即可，计算队列的大小，把元素全部放到辅助队列，剩余就是要弹出的元素，在将辅助队列赋值给队列，一个队列也可以实现
有效括号匹配：用栈解决该问题即可，栈可以用来解决对称匹配问题，就是对对碰，考虑清楚不匹配的情况，小技巧：匹配左括号，右括号进栈，最后对比元素是否与栈顶元素相等即可，遇左进栈，遇右弹出比较即可
删除字符相邻重复项：也是消除对称的匹配项，考虑栈来求解即可，最后字符串接收一下，注意字符串的顺序，需要反转一下
逆波兰表达式：其实就是后缀表达式，要知道后缀表达式可以不用考虑运算规则，也是遇到运算符进行消除操作，遇到运算符，将两个元素弹出，做相应的运算符操作即可，再压入栈中，不是运算符需要把字符串转成整形加入栈中，最后栈顶元素就是所求
滑动窗口最大值：需要自己实现一个单调队列，要实现功能：队头元素一直是最大的，这里为何不采用优先级队列，优先级队列可能打乱原本的顺序，所以自己实现一个单调队列即可，如果遍历的元素等于队头元素就从队头弹出，如果遍历的元素大于队尾元素，需要从队尾弹出，直到小于等于队尾元素，此时我们的队头元素就是所求，其实原理就是最大值中再找接下来的局部最大值，之后就是简单的运算，先将k个数字加入，得出来一个结果，在每次弹出一个元素，加入一个元素，即可，这道题很绕，真的值得好好细品！！！！！！！！
前k个高频元素：考的知识点很多：哈希表map,优先级队列，首先需要知道优先级队列，实现大根堆和小根堆区别，此题使用小根堆，我们需要前k高频，不然大根堆是留下低频，priority_queue（需要排序的类型，vector<类型>，规则（自定义）），这里为什么使用map因为需要下标和个数，下标就是key,个数就是value，哈希表进行优先级队里排序取k个元素就是前k个高频元素，这里要注意顺序，队头才是最高频的，所以队列 实现的题都很值得多思考，真的很绕，也容易想不到！！！！！！
