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.

Thoughts:

The key to this question lies in the design of minStack, push () pop () top () These operations are built-in Java Stack, do not have to say about it. The minStack record is always the smallest of all current elements, regardless of where minStack.peek () is in the stack.

Push(): When a new element is smaller than previous one, add it to minStack. The normal stack should keep adding new elements.

Pop(): Compare the two objects, pop from minStack and normal stack if they are equal. If not, always pop from the normal stack.

Java Solution:

public class MinStack { private Stackstack; private Stack minStack; public MinStack() { stack = new Stack (); minStack = new Stack (); } public void push(int x) { if(minStack.isEmpty() || x < minStack.peek()){ minStack.push(x); } stack.push(x); } public void pop() { if(stack.peek().equals(minStack.peek())){ minStack.pop(); } stack.pop(); } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } } //comment line

## No comments:

## Post a Comment