数据结构与算法——最小栈
程序员文章站
2022-03-11 23:32:05
...
题目
解题
1.利用两个栈,先将第一个元素入栈,第二个元素再进来的话就比较大小,如果比第一个大的话就放入第二个栈中。
2.后面每次进来的元素都与第一个栈中比大小,如果比第一个栈中的最上面的元素还要大的话就放到第二个栈的上面。
3.出栈的话,如果出第二个栈中的元素,第一个栈的顶部一直保存最小元素,出第一个栈中的元素的话,因为入栈的规则决定后入栈的元素都比先入栈的元素小,所以第一个栈中的顶部依旧保存最小元素。
4.获取栈中的最小值,即用peek获取第一个栈中顶部的元素。
Stack<int> stack=new Stack<int>();
Stack<int> minStack=new Stack<int>();
/** initialize your data structure here. */
public MinStack() {
}
public void Push(int x) {
if(minStack.Count==0)
minStack.Push(x);
else{
if(minStack.Peek()>=x)
{
minStack.Push(x);
}
}
stack.Push(x);
}
public void Pop() {
if(stack.Count==0) return;
var value=stack.Pop();
if(value==minStack.Peek())
minStack.Pop();
}
public int Top() {
return stack.Peek();
}
public int GetMin() {
return minStack.Peek();
}
}