一、最小栈
题目来源于:力扣
题目链接:传送门
题目介绍:
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
● MinStack() 初始化堆栈对象。
● void push(int val) 将元素val推入堆栈。
● void pop() 删除堆栈顶部的元素。
● int top() 获取堆栈顶部的元素。
● int getMin() 获取堆栈中的最小元素。
示例与解释:
输入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”] [[],[-2],[0],[-3],[],[],[],[]]
输出:
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
解题思路
采用两个栈的方式.
push_stack:用于正常的插入数据.
min_stack:用于记录当前栈最小值.
此方法需要注意最小栈(min_stack)的及时更新.
当我们执行压栈push操作时:
(1)min_stack:插入的第一个数据 或者 新插入的元素 < 当前栈的最小元素时,将待插入数据压栈.
(2)push_stack:用于正常的插入数据.
当我们执行压栈pop操作时:
(1) min_stack:如果删除的值==当前栈的最小值,则min_stack也要跟着删除.
(2)push_stack:用于正常的删除数据.
top():
返回 push_stack.top();即可.
getMin():
返回min_stack.top();即可.
示例图:
代码实现:
class MinStack { public: MinStack() { } void push(int val) { //第一个数据或者新插入的元素比当前栈的最小元素要小 if((push_stack.size()==0) ||(min_stack.top() >= val)) { min_stack.push(val); } push_stack.push(val); } void pop() { //如果删除的值是当前栈的最小值,则min_stack也要跟着删除 if(push_stack.top()==min_stack.top()){ min_stack.pop(); } push_stack.pop(); } int top() { return push_stack.top(); } int getMin() { return min_stack.top(); } private: stack<int> push_stack; stack<int> min_stack; };
二、栈的压入、弹出序列
题目来源于:牛客
题目链接:传送门
题目介绍:
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个在这里插入代码片序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
1.0<=pushV.length == popV.length <=1000
2.-1000<=pushV[i]<=1000
3.pushV 的所有数字均不相同
示例:
输入：
[1,2,3,4,5],[4,5,3,2,1]
返回值：
true
解释：
可以通过
push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列，返回true
解题思路
既然我们要判断是否是一个栈的出栈序列,我们可以通过模拟栈的出栈这种方式来判断.
1.创建一个栈,模拟进栈的过程.
2.每次入栈一个数据以后,判断与出栈序列首个元素是否相同.
3.不想同则表示此时不出栈,则继续入栈.
4.相同则表示此时可以出栈,则一直出栈直到不相同.
5.最后如果出栈序列走完了,则表明是正确的出栈序列.
代码实现
class Solution { public: bool IsPopOrder(vector<int>& pushV, vector<int>& popV) { stack<int> push_satck; int j=0; for(int i=0;i<pushV.size();i++) { push_satck.push(pushV[i]); while(push_satck.size()>0 && push_satck.top()==popV[j]) { push_satck.pop(); j++; } } // return j==popV.size(); if(j==popV.size()) { return true; } return false; } };
