【LeetCode】---15.最小栈
- 一、题目解析:
- 二、算法原理:
- 三、代码实现:
一、题目解析:
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
二、算法原理:
我们会单独开一个最小栈,来获得入栈里面中最小的元素:
但是有两个细节必须需要注意:
(1)当两个栈都为空的时候先入元素,然后将最小栈的栈顶元素和要入栈的元素进行对比,将最小值加入最小栈。
(2)如果要压入的元素都是最小值,最小值出现哪怕是多次,原来的栈要压入,最小栈也要压入,因为我们删除的时候不仅要删除原来的栈,还要删除最小栈的栈顶元素。
三、代码实现:
class MinStack
{
public:
MinStack()
{
}
void push(int val)
{
//当两个栈:st minst都是刚开始的时候为空的话,都先入一个元素
st.push(val);
if(minst.empty()||val<=minst.top())// 入val:(1)如果最小栈为空:入val(2)当入栈的val <= minst栈顶的最小值(注意val==minst.top()也要入栈!!!)
{
minst.push(val);
}
}
void pop()
{
//st.pop();// 这个表达式一定要在判断的后面!!!如果你都删完了,我还怎么判断?
if(minst.top()==st.top())
{
minst.pop();
}
st.pop();
}
int top()
{
return st.top();
}
int getMin()
{
return minst.top();
}
stack<int> st;
stack<int> minst;
};
/**
* 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();
*/