Question:
Design a stack that supports push, pop, top, and
retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
-------------------------------------------------------------------------
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
Answer: two stacks
Stack1 is an usual stack.
Stack2 is the smallest element stack.
Keeping top element of stack2 is smallest forever.
pop the smallest element of stack2 at the same time with stack1.
Code
class MinStack {
Stack<Integer> s1,s2;
public MinStack(){
s1=new Stack<>();
s2=new Stack<>();
}
public void push(int x) {
if(s2.isEmpty())
s2.push(x);
if(s2.peek()>x)
s2.push(x);
s1.push(x);
}
public void pop() {
if(s1.peek()==s2.peek())
s2.pop();
s1.pop();
}
public int top() {
return s1.peek();
}
public int getMin() {
return s2.peek();
}
}
网友评论