The general algorithm is great. At first, I thought you were overwriting the value with the min value, though, and it's because the fact that the Node stores two values is not very visible. A comment would help a lot here, and separating the logic in to a few lines too. This line:
s1.push(new Node(x,Math.min(s1.peek().min, x)));
should be:
int previousMin = backingStack.peek().minSoFar;
int minSoFar = Math.min(previousMin, value);
backingStack.push(new Node(value, minSoFar));
Note that I have also renamed all your variables. x
is a poor name for a value. An x
is a coordinate. s1
is another poor name, because where is s0
, s2
, etc... and what does s
mean? min
is not horrible, but it gives no indication of what it is the minimum of... what the context is.
Then, why are you using a Stack
as the back-end implementation? I know it seems logical to use java.util.Stack
, but you should know that it is not a recommended class any more. Stacks should be implemented over something that implements the Deque
interface like java.util.LinkedList
. The existing Stack
class is bad because it is based on top of Vector
which is a synchronized class that has a few implementation issues that are not recommended. The Stack class has this to say: "A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.". The Vector class has this to say: "Unlike the new collection implementations, Vector is synchronized. If a thread-safe implementation is not needed, it is recommended to use ArrayList in place of Vector."
So, Stack
is bad. I would use:
private final Deque<Node> stack = new LinkedList<>();
Now, about the pop()
method. It is a very C-like thing to split the pop()
and "get" methods. Java, and most other languages, return the top value with the pop()
call and avoid the need for a second call. Your pop()
should return a value. You also need an isEmpty()
Method so that people know when they have run out of data before they get a NoSuchElementException
.
Oh, and the Node
class can be private.
So, something like:
public class MinStack {
private final Deque<Node> stack = new LinkedList<>();
public void push(int value) {
if(stack.isEmpty()) {
stack.addFirst(new Node(value, value));
} else {
int minSoFar = Math.min(value, stack.getFirst().stackMin);
stack.push(new Node(value, minSoFar));
}
}
public boolean isEmpty() {
return stack.isEmpty();
}
public int pop() {
return stack.removeFirst().value;
}
public int peek() {
return stack.getFirst().value;
}
public int getMin() {
return stack.getFirst().stackMin;
}
private static class Node{
int value;
int stackMin;
public Node(int val, int min) {
value = val;
stackMin = min;
}
}
}