leetcode155. 最小栈
一、题目描述：计划一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
[*]MinStack() 初始化堆栈对象。
[*]void push(int val) 将元素val推入堆栈。
[*]void pop() 删除堆栈顶部的元素。
[*]int top() 获取堆栈顶部的元素。
[*]int getMin() 获取堆栈中的最小元素。
二、输入输出实例：
<strong>输入：</strong>
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],,[-3],[],[],[],[]]
<strong>输出：</strong>
<strong>解释：</strong>
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.三、思绪解说：
[*]创建两个stack对象，stack1用来存储入栈元素，stack2用来存储栈当前最小元素。
[*]push函数思绪：
①无论什么环境stack1都必要压栈。
②当stack2为空，或者stack2栈顶的元素和当前必要压栈的元素相等时，stack2执行压 栈操作。
[*]pop函数思绪：
①无论什么环境stack1都必要出栈。
②当stack2栈顶元素和stack1栈顶元素相等时，stack2执行出栈。
③当stack2不和stack1栈顶元素相等，分析要出栈的元素不是stack1栈中当前最小元素
那么这个元素可以直接弹出。
[*]构造函数可以删掉，删掉后编译器会生成默认构造函数；不删掉也可以不用剖析，由于这个类只有内置类型，所有内置类型都会自己走初始化列表。
[*]top函数返回stack1的栈顶元素即可。
[*]getMin返回stack2栈顶元素即可，stack2栈顶元素是当前栈中最小的元素。
四、C++代码：
class MinStack {
stack<int> s1;
stack<int> s2;
public:
MinStack()
{
//不用写，内置类型会自己走初始化列表
}
void push(int val)
{
s1.push(val);//主栈压栈
if(s2.empty()||val<=s2.top())//辅栈如果为空，或者val小于辅栈栈顶元素
//辅栈压栈
{
s2.push(val);
}
}
void pop()
{
if(s1.top()==s2.top())//如果主栈和辅栈的栈顶元素大小相等
//辅栈出栈
{
s2.pop();
}
s1.pop();//主栈无论如何都出栈
}
int top()//返回主栈的栈顶位置元素
{
return s1.top();
}
int getMin()//返回辅栈的栈顶元素，也就是主栈最小元素
{
return s2.top();
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]