目录
前言
在学习数据结构时，栈是一定会接触到的，栈本质是一个容器适配器，其使用起来也比较简单---满足先将后出的原则即可；关于stack的底层逻辑以及实现方法可见std::stack和std::queue-CSDN博客，栈实际上也能帮助我们解决一些特别的算法题，下面将具体剖析一些以栈为背景或使用栈来解决的题目。
PS：本篇博客中的所有题目均来自于灵茶山艾府 - 力扣（LeetCode）分享的题单。
栈基础题目
1441. 用栈操作构建数组
题解：题目能简单，本题是以栈为背景的一道题，但是在解题的过程中并不一定要使用栈，可以以一个数组来模拟栈。枚举1--n如果将每一个数字push，如果当前数字不在target中就pop。
class Solution {
public:
vector<string> buildArray(vector<int>& target, int n) {
int len=target.size(),j=0;
vector<string> ret;
for(int i=1;i<=n&&j<len;i++)
{
ret.push_back("Push"); //模拟push插入
if(i!=target[j]) //当前数字不在target中就pop
ret.push_back("Pop");
else j++; //否则找下一个target
}
return ret;
}
};844. 比较含退格的字符串
题解：此题就得#退格字符就类似于栈中将栈顶元素pop掉；所以可以使用一个栈来模拟文本编辑器，遍历字符如果是#就将栈顶元素删除，如果不是#就将字符入栈；最后将两个栈中的元素进行比较即可。
class Solution {
public:
bool backspaceCompare(string s, string t) {
stack<char> st1;
stack<char> st2;
for(auto e:s) //模拟文本编辑器
{
if(e=='#'&&!st1.empty()) st1.pop(); //是#进行删除
else if(e!='#') st1.push(e); //不是#将字符放入到栈中
}
for(auto e:t)
{
if(e=='#'&&!st2.empty()) st2.pop();
else if(e!='#') st2.push(e);
}
if(st1.size()!=st2.size()) return false; //如果栈中的元素个数不相等不可能满足条件
while(!st1.empty())
{
if(st1.top()!=st2.top()) return false; //检查每一次栈顶元素是否相等
st1.pop(),st2.pop();
}
return true;
}
};682. 棒球比赛
题解：记录得分的操作类似于栈，"+"取出两个栈顶元素将其相加放入到栈中，"D"取出栈顶元素将其翻倍，"C"间栈顶元素删除。所以可以使用stack对得分情况进行模拟。下面用vector来模拟stack因为在进行+操作时要读取末尾两个数据，使用数组更方便一些。
#include<ranges>
class Solution {
public:
int calPoints(vector<string>& operations) {
//记录得分的操作类似于栈
//"+"取出两个栈顶元素将其相加放入到栈中
//"D"取出栈顶元素将其翻倍
//"C"间栈顶元素删除
vector<int> st; //使用数组来模拟栈
for(auto& s:operations)
{
if(s=="+")
{
int n=st.size();
st.push_back(st[n-1]+st[n-2]);
}
else if(s=="D") st.push_back(st.back()*2);
else if(s=="C") st.pop_back();
else st.push_back(stoi(s));
}
int ret=0;
for(auto e:st) ret+=e;
return ret;
}
};2390. 从字符串中移除星号
题解：*移除前面的字符,不就是栈中移除栈顶元素嘛。可以使用string来模拟栈的实现，因为最终返回的类型的字符串所以此处直接用string模拟实现。
class Solution {
public:
string removeStars(string s) {
//*移除前面的字符,不就是栈中移除栈顶元素嘛
string ret;
for(auto ch:s)
{
if(ch=='*') ret.pop_back();
else ret.push_back(ch);
}
return ret;
}
};1472. 设计浏览器历史记录
题解：设计浏览器历史记录：可以使用两个栈来分别记录forward和back的网址，在用一个字符串记录当前所在网址即可。
class BrowserHistory {
//使用两个栈来实现
stack<string> _back; //back回退时访问的网站
stack<string> _forward; //forward前进时访问的网站
string now_str; //now_str表示当前访问的网站
public:
BrowserHistory(string homepage) {
now_str=homepage;
}
void visit(string url) {
while(!_forward.empty()) _forward.pop();
_back.push(now_str);
now_str=url;
}
string back(int steps) {
while(steps&&!_back.empty())
{
_forward.push(now_str); //间当前网址加入到forward队列中
now_str=_back.top(); //网址向后退,修改当前所在网址
_back.pop();
steps--;
}
return now_str;
}
string forward(int steps) {
while(steps&&!_forward.empty())
{
_back.push(now_str);
now_str=_forward.top();
_forward.pop();
steps--;
}
return now_str;
}
};
/**
* Your BrowserHistory object will be instantiated and called as such:
* BrowserHistory* obj = new BrowserHistory(homepage);
* obj->visit(url);
* string param_2 = obj->back(steps);
* string param_3 = obj->forward(steps);
*/946. 验证栈序列
题解：模拟栈的入栈和出栈。使用栈对pushed进行处理，当栈顶元素与popped队首元素相等时就出栈，知道最后一个元素入栈出栈后，判断栈是否为空即可。
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
//模拟栈的亚压栈和出栈操作
int n=pushed.size(),j=0;
stack<int> st; //用st来模拟栈
for(int i=0;i<n;i++)
{
st.push(pushed[i]);
while(!st.empty()&&st.top()==popped[j])
{
j++;
st.pop();
}
}
return st.empty();
}
};3412. 计算字符串的镜像分数
题解：哈希表+枚举右，维护左。在每一次挑选i和j的时候都是挑选的最接近的，挑选过的不能在继续挑选，所以需要使用哈希表存储i前面所有的字母以及下标。可以使用unordere_map<char ,vector<int>>其中char代表字符，用数组来存储下标。
class Solution {
public:
long long calculateScore(string s) {
//哈希表+枚举右,维护左
unordered_map<char,vector<int>> m; //存储右边存在的字符并记录下标位置
int n=s.size();
long long ret=0;
for(int i=0;i<n;i++)
{
char need='z'-s[i]+'a';
if(m.count(need))
{
ret+=i-m[need].back(); //将最接近的取出来
m[need].pop_back();
if(m[need].empty()) m.erase(need);
}
else m[s[i]].push_back(i); //将当前位置加入到哈希表中
}
return ret;
}
};71. 简化路径
题解：将每一个目录都进行分离并放入到栈中，如果出现".."就将栈顶元素删除，否则就将该路径放入到栈中。下面代码中使用数组来模拟栈。
class Solution {
public:
string simplifyPath(string path) {
//以/将每一个路径进行分割
//将说有路径都存放到栈中,如果出现..就出栈,否则就入栈
int n=path.size(),i=0;
vector<string> st;
while(i<n)
{
while(i<n&&path[i]=='/') i++;
int start=i;
while(i<n&&path[i]!='/') i++;
string tmp=path.substr(start,i-start); //分离出路径
if(tmp==".."&&!st.empty()) st.pop_back();
else if(tmp!="."&&tmp!="..") st.push_back(tmp);
}
//将栈中的元素读取出来
string ret;
for(auto& str:st)
if(str.size()) ret+='/'+str;
return ret==""?"/":ret;
}
};栈进阶
3170. 删除星号以后字典序最小的字符串
题解：删除所有的*，对于*来说删除其左边字典序最小的一个，删除完成后保证字符串的字典序最小。aaabadf*：当出现多个最小字符，如果要进行删除，必定删除最接近*的最小字符，而不是远离*的字符。
解题关键：可以使用26个栈来存放每个字符出现的位置，当遇到*的时候将最小字符进行删除即可。
class Solution {
public:
string clearStars(string s) {
int n=s.size();
unsigned int mask=0; //使用mask来记录栈是否为空,使用二进制的比特位来记录
vector<stack<int>> nums(26);
for(int i=0;i<n;i++)
{
if(s[i]=='*')
{
int k=countr_zero(mask); //使用内置函数countr_zero找第一个不为1二进制位,即第一个不为空的栈
auto& st=nums[k];
s[st.top()]='0';
st.pop();
if(st.empty()) mask^=1<<k;
}
else
{
nums[s[i]-'a'].push(i);
mask|=1<<(s[i]-'a');
}
}
string ret;
for(auto e:s)
if(e!='0'&&e!='*') ret+=e;
return ret;
}
};155. 最小栈
题解：创建一个最小栈，能够在参数级别的时间内获得最小元素。这就意味这必须对最小元素进行存储，并且当最小元素被pop后还能在参数级时间内找到其余的最小元素。
使用两个栈进行存储，其中普通栈正常存储，插入，删除。对于最小栈只有当栈位空或插入元素比栈顶元素小的时候才插入。
插入：当插入遇元素小于最小栈的时候，才插入到最小栈中；
删除：当删除的栈顶元素与最小栈的栈顶元素相等时，才对最小栈进行删除。
class MinStack {
stack<int> st; //普通栈,存储每一个元素
stack<int> min; //最小栈,只存储最小元素,栈顶永远是最小元素
public:
MinStack() {}
void push(int val) {
if(min.empty()||min.top()>=val) min.push(val);
st.push(val);
}
void pop() {
if(min.top()==st.top()) min.pop();
st.pop();
}
int top() {
return st.top();
}
int getMin() {
return min.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/1381. 设计一个支持增量操作的栈
题解：直接使用一个数组来模拟栈即可。
class CustomStack {
vector<int> st;
int num;
public:
CustomStack(int maxSize) {
num=maxSize;
}
void push(int x) {
if(st.size()==num) return ;
st.push_back(x);
}
int pop() {
if(st.empty()) return -1;
int ret=st.back();
st.pop_back();
return ret;
}
void increment(int k, int val) {
for(int i=0;i<k&&i<st.size();i++)
st[i]+=val;
}
};
/**
* Your CustomStack object will be instantiated and called as such:
* CustomStack* obj = new CustomStack(maxSize);
* obj->push(x);
* int param_2 = obj->pop();
* obj->increment(k,val);
*/636. 函数的独占时间
题解：模拟+栈。因为函数调用要进行压栈和出栈，所以可以用栈来模拟函数的调用。注意：将时间和函数编号分开处理否则很容易混淆。栈中存储函数调用，时间只需要用一个变量prev来记录上一个时刻即可。
根据上面图示，只需要将时间分块处理即可，如何获取每一个时间块的时间：使用一个变量prev纪录上一个时间点即可，大体上分为两种情况：
- 是start开始调用位置，如果前面已经有函数即栈不为空，则上一个[prev,now)属于上一个函数调用的时间，即ret[st.top()]+=now-prev；并将该函数入栈；
- 是end函数调用结束，则[prev,end]属于当前函数调用得时间，ret[index]+=end-prev+1，将上一个函数出栈。
如何在一个字符串中获取编号和时间？？？
sscanf(const char *str, const char *format, ...)
第一个参数str是要进行提取得字符串，后面得参数是可变参数。
%[^:]表示到：的所以字符都取到，log.c_str()是string的函数转为char *str格式的。所以上面得提取可以写做：sscanf(str.c_str,"%d:%[^:]:%d",&index,type,%time)；
class Solution {
public:
vector<int> exclusiveTime(int n, vector<string>& logs) {
//使用一个长度为n的数组存储结果
//因为函数的调用要通过压栈的出栈来实现,这就类似于栈的先进后出的模式,所以可以使用栈来模拟函数调用
//栈中要存放两个数据:函数编号,起始时间
vector<int> ret(n);
stack<int> st;
int prev=0;
for(auto& str:logs)
{
int index,time;
char type[10];
sscanf(str.c_str(),"%d:%[^:]:%d",&index,type,&time);
if(type[0]=='s')
{
if(!st.empty()) ret[st.top()]+=time-prev;
st.push({index});
prev=time;
}
else
{
ret[index]+=time-prev+1;
st.pop();
prev=time+1;
}
}
return ret;
}
};2434. 使用机器人打印字典序最小的字符串
题解：弹性+栈。"zza"我们让s中a加入到t中时才将字符写到纸上。"caba"进行处理的时候也是显然"ca"加到t中出"a"，然后选择是出"c"还是继续入栈，发现后面还有"b更小的，所以继续入栈。总而言之我们一直将栈顶的元素与s剩余的字符比较，如果栈顶元素小，出栈，否则继续入栈。
class Solution {
public:
string robotWithString(string s) {
vector<int> ch(26); //存放s中各个字符的个数
int n=s.size();
auto get_min=[&]()->char //获取s中剩余字符串的最小值
{
for(int i=0;i<26;i++)
if(ch[i]>0) return 'a'+i;
return '0';
};
for(auto e:s) ch[e-'a']++; //将s中的字符串存储起来
string ret,t;
for(int i=0;i<n;i++)
{
t.push_back(s[i]); //将当前字符从s中加入到t中
ch[s[i]-'a']--;
while(t.size()&&t.back()<=get_min()) //如果t栈顶的元素小于等于s剩余元素,则可以直接出了
{
ret.push_back(t.back());
t.pop_back();
}
}
while(t.size()) //将t中剩余的字符加入到答案中
{
ret.push_back(t.back());
t.pop_back();
}
return ret;
}
};895. 最大频率栈
题解：可以直接进行暴力处理，将所有元素都统计到数组中，每一次遍历数组删除出现次数最多的元素。
class FreqStack {
vector<pair<int,int>> nums; //存储每一个元素,以及出现的次数
int max_count=0; //存储最大出现次数
public:
FreqStack() {}
void push(int val) {
int count=0;
for(auto& [x,y]:nums)
if(x==val) y++,count++; //将数组中等于val的值个数+1
nums.push_back({val,count+1});
max_count=max(max_count,count+1);
}
int pop() {
for(auto it=nums.rbegin();it!=nums.rend();it++)
{
if(it->second==max_count) //找到了要进行删除的元素
{
int ret=it->first;
nums.erase((++it).base()); //将其进行删除
max_count=0;
for(auto& [x,y]:nums) //将nums中的元素的数目进行改变
{
if(x==ret) y--;
max_count=max(max_count,y);
}
return ret;
}
}
return -1;
}
};
/**
* Your FreqStack object will be instantiated and called as such:
* FreqStack* obj = new FreqStack();
* obj->push(val);
* int param_2 = obj->pop();
*/此方法不论是pop还是push的时间复杂度都是O(N)，能否进行优化？？？
哈希表+栈：使用哈希表存储每一个数字出现的次数，用多个栈来存储出现相同次数的数字即可。
unordered_map<int,int> m;用来存储每一个字母出现的次数，vector<stack<int>> 用来存储出现相同次数的元素。
class FreqStack {
unordered_map<int,int> m; //存储每一个元素出现的次数
vector<stack<int>> nums; //存储出现次数相同的数字
public:
FreqStack() {
nums.push_back(stack<int>());
}
void push(int val) {
m[val]++; //加入该数字
if(m[val]==nums.size()) //栈的数量不够了
nums.push_back({});
nums[m[val]].push(val);
}
int pop() {
int ret=nums.back().top();
nums.back().pop();
if(nums.back().size()==0) nums.pop_back();
m[ret]--;
return ret;
}
};
/**
* Your FreqStack object will be instantiated and called as such:
* FreqStack* obj = new FreqStack();
* obj->push(val);
* int param_2 = obj->pop();
*/1172. 餐盘栈
餐盘栈，找到指定的位置出栈，还要找到第一个为空的栈来入栈。
如果直接维护维护一个vector<stack<int>> 的数组：那么找第一个为空的栈时时间时间复杂度是O(N)会出现超时。
那如何能够找到第一个不满的栈呢？？？
如果要找第一个不满的栈，当这个栈存满的又要找下一个不满的栈；那何不直接将所有未满的栈全都存储起来。还要能找到最小的栈，那不就是最小堆吗！！！
当进行pop的时候可能会导致数组长度减少，而在插入push的时候我们使用的下标是pq.top()即pq中的最小值，所以在进行插入的时候要检查pq.top()和nums.size()的大小关系，防止pq.top()访问是越界，如果pq.top()>=nums.size()说明堆中所有元素都越界了，直接全出完。
class DinnerPlates {
priority_queue<int,vector<int>,greater<int>> pq; //存储不满的栈
vector<stack<int>> nums; //存储所有的栈
int max_size;
public:
DinnerPlates(int capacity) {
max_size=capacity;
}
void push(int val) {
if(!pq.empty()&&pq.top()>=nums.size()) //如果堆中最小值比数组长度大,说明堆中所有元素都不满足
while(!pq.empty()) pq.pop();
if(pq.empty())
{
//全部栈都是满的,在数组后面再加一个栈
nums.push_back({});
nums.back().push(val);
if(nums.back().size()!=max_size) pq.push(nums.size()-1);
}
else
{
int pos=pq.top();
nums[pos].push(val);
if(nums[pos].size()==max_size) pq.pop(); //如果满了就将其移除堆
}
}
int pop() {
return popAtStack(nums.size()-1);
}
int popAtStack(int index) {
if(nums.size()<=index||nums[index].empty()) return -1;
int ret=nums[index].top();
if(nums[index].size()==max_size) pq.push(index);
nums[index].pop();
while(nums.size()&&nums.back().empty()) nums.pop_back(); //如果最后一个栈为空,直接将其移除数组
return ret;
}
};
/**
* Your DinnerPlates object will be instantiated and called as such:
* DinnerPlates* obj = new DinnerPlates(capacity);
* obj->push(val);
* int param_2 = obj->pop();
* int param_3 = obj->popAtStack(index);
*/总结
栈类型的题目分为两种：以栈为背景，实现一个新的栈或使用栈来处理数据。栈类型题目大部分不会单独出，而是结合其他数据结构来出。总而言之，栈类型的题目简单就很简单，但是如果结合其他题目也会很难。所以在处理栈类型题目的时候，将题目简化，分类处理就很重要。