栈与队列codetop+代码随想录刷题大总结，秋招会这几题就够啦！！！！

纯个人总结，主要供自己回顾复习(´ο｀*）~

1.基本计算器
2.基本计算器II
3.字符串解码
4.删除字符串中所有相邻重复项II
5.去除重复字母
6.最小栈
7.股票价格跨度

1.基本计算器

字符串转整数：用(a - ‘0’)

for(int i = 0; i < s.size(); i ++){char c = s[i];n = 10 * n + (c - '0');

只考虑有加减法，没有括号没有乘除

stack<int> stk;
char sign = '+';
//遇到加减法转数组
for(int i = 0; i < s.size(); i ++){char c = s[i];if(isdigit(c)) num = 10 * num + (c - '0');//解决2个数的情况if(c == '+' || c == '-' || i == s.size() - 1){switch(sign){case '+':stk.push(num);break;case '-':stk.push(-num);break;}sign = c;num = 0;//重置num！！！！}
}
//将栈中所有结果求和就是答案
int res = 0;
while(!stk.empty()){res += stk.top();stk.pop();
}
return res;

考虑情况加上乘除法
在switch的部分加上两种情况即可

if(c == '+' || c == '-' || c == '/' || c == '*' || i == s.size() - 1){int pre;switch(sign){case '+':stk.push(num); break;case '-':stk.push(-num); break;case '*':pre = stk.top(); stk.pop();stk.push(num * pre);break;case '/':pre = stk.top(); stk.pop();stk.push(pre / num);break;}sign = c;num = 0;
}

处理括号：定义一个函数_calculate，接收三个参数，字符串s，以及字符串左右边界start和end，这样就可以计算 s 中任意一个子表达式的值了。括号具有递归的性质，括号包含的算式，我们直接视为一个数字就行了。

class Solution {
public:int calculate(string s) {// key 是左括号的索引，value 是对应的右括号的索引unordered_map<int, int> rightIndex;// 利用栈结构来找到对应的括号stack<int> stack;for (int i = 0; i < s.length(); i++) {if (s[i] == '(') {stack.push(i);} else if (s[i] == ')') {rightIndex[stack.top()] = i;stack.pop();}}return _calculate(s, 0, s.length() - 1, rightIndex);}private:// 定义：返回 s[start..end] 内的表达式的计算结果int _calculate(string s, int start, int end, unordered_map<int, int> &rightIndex) {// 需要把字符串转成双端队列方便操作stack<int> stk;// 记录算式中的数字int num = 0;// 记录 num 前的符号，初始化为 +char sign = '+';for (int i = start; i <= end; i++) {char c = s[i];if (isdigit(c)) {num = 10 * num + (c - '0');}if (c == '(') {// 递归计算括号内的表达式num = _calculate(s, i + 1, rightIndex[i] - 1, rightIndex);i = rightIndex[i];}if (c == '+' || c == '-' || c == '*' || c == '/' || i == end) {int pre;switch (sign) {case '+':stk.push(num);break;case '-':stk.push(-num);break;// 只要拿出前一个数字做对应运算即可case '*':pre = stk.top(); stk.pop();stk.push(pre * num);break;case '/':pre = stk.top(); stk.pop();stk.push(pre / num);break;}// 更新符号为当前符号，数字清零sign = c;num = 0;}}// 将栈中所有结果求和就是答案int res = 0;while (!stk.empty()) {res += stk.top();stk.pop();}return res;}
};

完整代码，需要非常细心：

class Solution {
private:int _calculate(string s, int start, int end, unordered_map<int, int> leftToRight){stack<int> stk;int num = 0;char sign = '+';for(int i = start; i <= end; i ++){char c = s[i];if(isdigit(c)) num = num * 10 + (c - '0');if(c == '('){num = _calculate(s, i + 1, leftToRight[i] - 1, leftToRight);i = leftToRight[i];// 更新索引，跳过已经处理过的括号部分}if(c == '+' || c == '-' || c == '*' || c == '/' || i == end ){int pre;switch(sign){case '+':stk.push(num); break;case '-':stk.push(-num); break;case '*':pre = stk.top();stk.pop();stk.push(pre * num);break;case '/':pre = stk.top();stk.pop();stk.push(pre / num);break;}num = 0;sign = c;}}int res = 0;while(!stk.empty()){res += stk.top();stk.pop();}return res;}
public:int calculate(string s) {//利用栈的特性来存左右括号的索引stack<int> stk;unordered_map<int, int> leftToRight;for(int i = 0; i < s.size(); i ++){if(s[i] == '(') stk.push(i);else if(s[i] == ')'){leftToRight[stk.top()] = i;stk.pop();}}return _calculate(s, 0, s.size() - 1, leftToRight);}
};

2.基本计算器II

II比I更简单，不考虑括号情况，值得注意的是，不要忘记i == s.size() - 1的时候是最后一次计算

class Solution {
public:int calculate(string s) {int num = 0;stack<int> stk;char sign = '+';for(int i = 0; i < s.size(); i ++){int pre;if(isdigit(s[i])) num = num * 10 + (s[i] - '0');if(s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || i == s.size() - 1){switch(sign){case '+':stk.push(num);break;case '-':stk.push(-num);break;case '*':pre  =  stk.top();stk.pop();stk.push(pre * num);break;case '/':pre = stk.top();stk.pop();stk.push(pre / num);break;}num = 0;sign = s[i];}}int res = 0;while(!stk.empty()){res += stk.top();stk.pop();}return res;}
};

3.字符串解码

和基本计算器非常相似

class Solution {
private:// 解决 k[string] 的问题string _decodeString(string s, int start, int end, unordered_map<int, int> &leftToRight) {string res = ""; // 解码后的字符串int num = 0;     // 重复次数for (int i = start; i <= end; i ++) {if (isdigit(s[i])) {num = num * 10 + (s[i] - '0'); // 记录重复次数}else if (s[i] == '[') { // 递归解码括号内的部分string decode = _decodeString(s, i + 1, leftToRight[i] - 1, leftToRight);i = leftToRight[i]; // 更新 i 为与当前 [ 对应的 ] 的位置// 解决完一个 k[string]，开始解码while (num > 0) {res += decode;num--;}}else { // 普通字符直接添加到结果res += s[i];}}return res;}public:string decodeString(string s) {// 用栈的特性来找到左右的方括号索引stack<int> stk;unordered_map<int, int> leftToRight;for (int i = 0; i < s.size(); i++) {if (s[i] == '[') {stk.push(i);} else if (s[i] == ']') {leftToRight[stk.top()] = i; // 记录 [] 的索引stk.pop();}}// 从整个字符串开始递归解码return _decodeString(s, 0, s.size() - 1, leftToRight);}
};

4.删除字符串中所有相邻重复项II

给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。
eg：
输入：s = “pbbcggttciiippooaais”, k = 2
输出：“ps”

看起来很可怕，但其实就是频率等于k的全不要，大于k的减掉k个而已，入栈的同时记录一下频率即可

class Solution {
public:string removeDuplicates(string s, int k) {stack<pair<char, int>> stk;for (int i = 0; i < s.size(); i++) {// 检查栈是否为空或栈顶元素是否与当前字符相同if (!stk.empty() && stk.top().first == s[i]) {stk.top().second++; // 增加计数} else {stk.push({s[i], 1}); // 如果栈为空或者字符不同，压入栈}// 如果栈顶元素的计数等于 k，弹出该元素if (stk.top().second == k) {stk.pop();}}// 拼接答案string res = "";while (!stk.empty()) {res.append(stk.top().second, stk.top().first); // 按照计数拼接字符stk.pop();}reverse(res.begin(), res.end()); // 结果需要反转，因为栈是后进先出return res;}
};

append函数讲解：

append() 的用法：
string 提供了多个重载的 append() 函数，常见的几种用法如下：1. 追加一个字符串：
string str1 = "Hello";
string str2 = "World";
str1.append(str2);  // str1 变为 "HelloWorld"
str1.append(" World");  // str1 变为 "Hello World"
str1.append(str2, 0, 3);  // 追加 str2 从索引 0 开始的 3 个字符，str1 变为 "HelloWor"2. 追加指定次数的字符：
string str = "A";
str.append(5, 'B');  // 在 str 后追加 5 个 'B'，str 变为 "ABBBBB"

5.去除重复字母

给定字符串 s，删除重复的字母，使每个字母只出现一次。你必须确保你的结果是 "按词典顺序排列的最小"在所有可能的结果中。

首先用不了sort，因为是在原始顺序的基础上输出的字典序最小排列。
使用一个count数组来记录每个字母出现的次数。使用一个bool数组来记录某个字母是否已经出现在栈中，确保每个字母只出现一次。

遍历字符串：
对于每个字母，如果该字母已在栈中，跳过
如果该字母比栈顶字母小，并且栈顶字母在后面还会出现，则将栈顶字母移除（以确保字典序最小）。

保证字典序最小，移除不合适的栈顶元素关键代码：

//要一直移除,直到没有不合适的
while(!stk.empty() && c < stk.top() && count[stk.top() - 'a'] > 0){visited[stk.top() - 'a'] == false;stk.pop();
}
stk.push(c);

全部代码：

class Solution {
public:string removeDuplicateLetters(string s) {stack<char> stk;vector<int> count(26, 0);//需要一个count数组存剩下出现次数vector<bool> visited(26, false);//需要一个visited数组存栈中是否存在for(char c : s) count[c - 'a'] ++;for(char c : s){count[c - 'a'] --;if(visited[c - 'a']) continue;while(!stk.empty() && stk.top() > c && count[stk.top() - 'a'] > 0){visited[stk.top() - 'a'] = false;stk.pop();}stk.push(c);visited[c - 'a'] = true;}string res = "";while(!stk.empty()){res += stk.top();stk.pop();}reverse(res.begin(), res.end());return res;}
};

6.最小栈

简单来说，需要通过设计了来返回栈中最小值
可以多次调用 getMin，并且每次都会返回当前最小的元素。

class MinStack {stack<int> stk;stack<int> minstack;
public:MinStack() {}void push(int val) {stk.push(val);if(minstack.empty() || minstack.top() >= val) minstack.push(val);}void pop() {if(stk.top() == minstack.top()) minstack.pop();stk.pop();}int top() {return stk.top();}int getMin() {return minstack.top();}
};

7.股票价格跨度

涉及一个算法收集某些股票的每日报价，并返回该股票当日价格的跨度。
当日股票价格的跨度被定义为股票价格小于等于今天价格的最大连续日数(从今天开始往回数，包括今天)
例如：
如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]
那么股票跨度将是 [1,1,1,2,1,4,6] 。

单调栈，左边第一个大的数

class StockSpanner {
private:stack<pair<int, int>> stk;
public:StockSpanner() {}int next(int price) {int span = 1;while(!stk.empty() && stk.top().first <= price){span += stk.top().second;stk.pop();}stk.push({price, span});return span;}
};