引言
栈类型的题目应该是面试中比较常见的，毕竟思路对了基本马上可以做出来。关键其实只是对于堆的思路的理解。此处在总结栈类型的题目的时候也把队列也一并介绍
- 栈（stack）是先入后出的
- 队列（queue）是先入先出的
- 双端队列（dueue）则是两端都可了~
更直观的请见下图
下图更加直观的展示了栈和队列的区别
下面则详细的列举了定义及函数的使用：
有效括号
class Solution {
public:
bool isValid(string s) {
stack<char> group;
for(int i=0;i<s.size();i++)
{
if(s[i]=='(' || s[i]=='[' || s[i]=='{')
group.push(s[i]);
else
{
if(!group.empty())//若不为空
{
if(
(s[i]==')' && group.top()=='(')
||(s[i]==']' && group.top()=='[')
||(s[i]=='}' && group.top()=='{')
)
group.pop();//找了就删掉
else //找不到匹配的就不是
return false;
}
else
return false;
}
}
if(group.size()) //结束后如果不是空的，
return false;
else
return true;
}
};
最长有效括号
保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」这样才是连续成对的。空间复杂度和时间复杂度都为O（N）
class Solution {
public:
int longestValidParentheses(string s) {//输入为只包含 '(' 和 ')' 的字符串
int max_len=0;//最长有效（格式正确且连续）
stack<int> stack_index;//记录index索引的
stack_index.push(-1);//初始化先push一个-1的索引。作为「最后一个没有被匹配的右括号的下标」
//左右括号成一对，记录的是当前的右括号与上一个不成对的右括号
for(int i=0;i<s.size();i++)
{
if(s[i]==')')//若是右括号
{
stack_index.pop();//删掉这个右括号前一个的左括号（弹出一个栈顶表示匹配了当前的括号！）
if(!stack_index.empty())//若不为空
{
int range=i-stack_index.top();
max_len=max(max_len,range);//记录连续的～
}
else//若为空说明：当前的右括号为没有被匹配的左括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
stack_index.push(i);//存入，这个右括号的索引。为当前最后一个没有被匹配的右括号（下次会先删除）
}
else
stack_index.push(i);//存入左括号的索引
}
return max_len;
}
};
移掉K位数字
需要先解读题目，数字应该是顺序不变的。那要保证尽量递增的形式.且要避免前导为0（也就是栈为空时，0不要放入）
class Solution {
public:
string removeKdigits(string num, int k) {
stack<char> stack_char;
for(int i=0;i<num.size();i++)
{
//每次先检查，如果满足可以先从栈中删除一些：满足条件：从左到右为递增（小的放前面）
while(!stack_char.empty() && k>0 && stack_char.top()>num[i])
{
// 当盏不为空，且盏顶的元素大于当前的元素的时候，把栈顶的元素去掉。放入当前的元素
stack_char.pop();
k--;//计数值自减
}
if(stack_char.empty() && num[i]=='0')//避免了前导为0
continue;//跳过第一个为0
stack_char.push(num[i]);//每次都将当前值放入
}
string result;//记录结果
while(!stack_char.empty())
{
if(k>0)//如果还需要继续删除位数
k--;
else //只有当不需要去除数字的时候才加入
result+=stack_char.top();//注意这个比下面的空间复杂度更低
// result=stack_char.top()+result; //每次赋值导致更高的内存消耗
stack_char.pop();//弹出栈顶
}
//栈是反过来的因此需要反转一下
reverse(result.begin(), result.end());//stl中的reverse函数，需要反转一下。因为栈是逆过来的
return result.empty()? "0":result;//注意最后结果是否为空
}
};
string代替栈：去掉重复字母
class Solution {
public:
string removeDuplicateLetters(string s) {
//先通过unordered_map记录每个字符出现了多少次
unordered_map<char,int> map;
for(auto str:s)
map[str]++;
stack<char> stack_str;//定义一个栈
unordered_map<char,int> map_stack;//用于记录这个字符是否在栈中
for(int i=0;i<s.size();i++)
{
if(map_stack[s[i]]>0)//当前已经存在于stack中了
{
map[s[i]]--;
continue;
}
//否则就是不存在了~
while(!stack_str.empty() && stack_str.top()>s[i] && map[stack_str.top()]>0)
{//当前盏不为空，且top的元素大于s[i]，且stack_str.top()元素数量大于0，也就是后面还有
map_stack[stack_str.top()]=0;//记录（不在栈中）
stack_str.pop();//出栈
}
stack_str.push(s[i]);//入栈
map_stack[s[i]]=1;//入栈记录
map[s[i]]--;//也要记录
}
string output_str;
while(!stack_str.empty())
{
output_str=stack_str.top()+output_str;//注意顺序就不需要采用reverse
stack_str.pop();
}
return output_str;
}
};
上面方法虽然通过栈可以解决，但是却很容易出错，还需要额外记录。因此下面给出用string的解法。其实也是用了栈的思想，只是用了string可以用其函数find这样可以简化操作
class Solution {
public:
string removeDuplicateLetters(string s) {
// 注意要求是字典序最小其不能打乱字符，单纯的unordered_map解决不了~
// 对于输入bcabc。第一个是b放入，第二个发现是c，b<c,也将c放入
// 当遇到a，少于c,且a后面有c，所以c删掉。小于b，所以b删掉。
//先通过unordered_map记录每个字符出现了多少次
unordered_map<char,int> map;
for(auto str:s)
{
map[str]++;
}
string output_str;
for(int i=0;i<s.size();i++)
{
//说明当前字符已经存在了，故此不再插入
if(output_str.find(s[i])!=string::npos)
{
map[s[i]]--;//记录这个字符的数目减一，虽然没有入栈，但是这个字符也被剔除掉了
continue;
}
//如果没有找到
//且栈内不为空，且即将进栈的元素小于当前栈顶的元素，同时当前栈顶的元素也不是最后一个（map中还有）
while(!output_str.empty() && output_str.back()>s[i] && map[output_str.back()]>0)
{
//循环对比
output_str.pop_back();//就可以删掉（相当于出栈）
//注意由于原本这个字符入栈的时候已经减一了，所以这里不需要再减一
}
output_str.push_back(s[i]);//入栈操作
map[s[i]]--;//入栈后减一。
}
return output_str;
}
};
简化路径
时间与空间复杂度都是O（N）
class Solution {
public:
string simplifyPath(string path) {
// if(path.back()!='/')
// path=path+'/';//在结尾处加上'/'方便对路径的字母进行分组放于str_group中
vector<string> str_group;
string temp_str;
for(int i=0;i<path.size();i++)//进行路径的分割
{
if(path[i]=='/') //遇到斜杆
{
if(!temp_str.empty())//如果不为空就push到vector中
{
str_group.push_back(temp_str);
temp_str.clear();//清空一下
}
}
else
temp_str=temp_str+path[i];
}//这样就实现了以斜杆划分,并且不包含斜杆
//存入最后一个
if(!temp_str.empty())
str_group.push_back(temp_str);//若不为空，存进去（不要漏掉了！！！）
stack<string> path_stack;//定义栈
for(int i=0;i<str_group.size();i++)//遍历分割后的路径
{
string temp_str=str_group[i];;
// if(!temp_str.empty())//作为double check
// {
if(temp_str==".")//若为一个点，不处理
{}
else if (temp_str=="..")//如果连续两个点，那么就是要切换到上一级目录
{
if(!path_stack.empty())//如果栈不为空，就把栈顶删掉
path_stack.pop();
}
else//上面都不满足，就应该是正常字符，所以输入作为路径
path_stack.push(temp_str); //放入栈中
// }
}
//最终结果存放到string中
string output_str;
while(!path_stack.empty())
{
output_str = "/" + path_stack.top() + output_str;//注意顺序,加到当前的前面
path_stack.pop();
}
return output_str.empty()? "/":output_str;//若为空那么只有一个斜杆
}
};
矩阵乘法计算量估算
时间复杂度和空间复杂度都为O（N）关键点是：1、每对括号包含两个矩阵。2、矩阵的乘法数量应该是matrix_1.second*matrix_2.second*matrix_1.first也就是三个不一样的数字相乘啦
#include <iostream>
#include <utility>
#include <vector>
#include <stack>
using namespace std;
int main() {
int num;
cin>>num;
vector<pair<int,int>>matrix_group;
for(int i=0;i<num;i++)
{
int a,b;
cin>>a>>b;
auto each=make_pair(a, b);
matrix_group.push_back(each);
}
string input_str;
cin>>input_str;
stack<pair<int,int>> string_stack;//定义一个栈来存行列
int result=0;
for(int i=0,j=0;i<input_str.size();i++)
{
if(input_str[i]=='(')//找到一个左括号，不做任何操作
{
int do_nothing;
}
else if(input_str[i]==')')//找到一个右括号，先出栈2个，必然为2个！！！！！
{
if(!string_stack.empty())
{
auto matrix_2=string_stack.top();
string_stack.pop();//取出后删掉
auto matrix_1=string_stack.top();
string_stack.pop();//取出后删掉
//注意矩阵乘法的数目，
result+=matrix_1.second*matrix_2.second*matrix_1.first;//matrix_1.second=matrix_2.first
auto each_new=make_pair(matrix_1.first, matrix_2.second);
string_stack.push(each_new);
}
}
else {//入栈
string_stack.push(matrix_group[j]);
j++;
}
}
std::cout<<result;
}