栈算法合集

一. 232. 用栈实现队列题目要求请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty实现 MyQueue 类void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空返回 true 否则返回 false1. 正常做法classMyQueue{public:stackintout;//输出栈stackintin;//输入栈MyQueue(){}voidpush(intx){//将元素 x 推到队列的末尾if(out.empty()){out.push(x);}elsein.push(x);}intpop(){//从队列的开头移除并返回元素inttempout.top();out.pop();if(out.empty()){while(!in.empty()){out.push(in.top());in.pop();}}returntemp;}intpeek(){//返回队列开头的元素returnout.top();}boolempty(){return(in.empty()out.empty());}};二. 20. 有效的括号题目要求给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串 s 判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。1. 栈做法classSolution{public:boolisValid(string s){stackchartemp;for(autoe:s){if(e(||e{||e[)temp.push(e);else{// if(e) || e} || e])// 在访问栈顶前检查栈是否为空if(temp.empty())//还没遍历完已经没有左括号匹配了returnfalse;//不是有效的if((e)temp.top()()||(e}temp.top(){)||(e]temp.top()[)){temp.pop();}else{returnfalse;}}}if(temp.empty())//所有元素被比较完了,符合要求有效returntrue;//避免[()returnfalse;}};2. 哈希表做法classSolution{public:boolisValid(string s){intns.size();if(n%21){returnfalse;}unordered_mapchar,charpairs{{),(},{],[},{},{}};stackcharstk;for(charch:s){if(pairs.count(ch)){if(stk.empty()||stk.top()!pairs[ch]){returnfalse;}stk.pop();}else{stk.push(ch);}}returnstk.empty();}};三. 155. 最小栈题目要求设计一个支持 push pop top 操作并能在常数时间内检索到最小元素的栈。实现 MinStack 类:MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。常数时间内检索到最小元素的栈要求O(1)而不是全部遍历一遍1. 两个栈/* 主栈和最小栈查看最小元素用最小栈删除主栈的栈顶元素时也要更新最小栈的栈顶元素 比如入栈-2 0 -3 主栈为[-2, 0, -3] 最小栈为[-2, -2, -3] */classMinStack{public:stackintmain_stack;stackintmin_stack;MinStack(){}voidpush(intval){main_stack.push(val);if(min_stack.empty())min_stack.push(val);elsemin_stack.push(min(val,min_stack.top()));}voidpop(){min_stack.pop();main_stack.pop();}inttop(){returnmain_stack.top();}intgetMin(){returnmin_stack.top();}};2. 一个栈classMinStack{public:stackpairint,intmain_stack;MinStack(){}voidpush(intval){int_firstval;int_second;if(main_stack.empty())_secondval;else_secondmin(val,main_stack.top().second);pairint,inttemp{_first,_second};main_stack.push(temp);}voidpop(){main_stack.pop();}inttop(){returnmain_stack.top().first;}intgetMin(){returnmain_stack.top().second;}};四. 739. 每日温度题目要求给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用 0 来代替。1. 单调栈classSolution{public:vectorintdailyTemperatures(vectorinttemperatures){intntemperatures.size();// 1. 初始化答案数组全设为 0兜底策略如果没人比它热默认就是 0vectorintret(n,0);stackintst;// 2. 开辟单调栈千万记住里面存的是【索引】for(inti0;in;i){// 只要栈不为空且“新人”的温度 “栈顶”的温度while(!st.empty()temperatures[i]temperatures[st.top()]){inttempi-st.top();// 计算相隔天数记入答案ret[st.top()]temp;st.pop();}st.push(i);}returnret;}};