Stack Min:
How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element? Push, pop and min should all operate in 0(1) time.
If we kept track of the minimum at each state, we would be able to easily know the minimum. We can do this by having each node record what the minimum beneath itself is. Then, to find the min, you just look at what the top element thinks is the min.
When you push an element onto the stack, the element is given the current minimum. It sets its "local min"to be the min.
public class StackWithMin extends Stack<NodeWithMin> {
public void push(int value) {
int newMin = Math.min(value, min());
super.push(new NodeWithMin(value, newMin) );
}
public int min() {
if (this . isEmpty()) {
return Integer.MAX_VALUE // Error value
} else {
return peek().min;
}
}
}
class NodeWithMin {
public int value;
public int min;
public NodeWithMin(int v, int min) {
value = v;
this.min = min;
}
}
There's just one issue with this: if we have a Iarge stack, we waste a lot of space by keeping track of the min for every single element. Can we do better?
We can (maybe) do a bit better than this by using an additional stack which keeps track of the mins.
public class StackWithMin2 extends Stack<Integer> {
Stack<Integer> s2;
Stack<Integer> s2(){
s2 = new Stack<Integer>();
}
public void push(int value){
if (value <= min) {
s2.push(value);
}
super.push(value);
}
public Integer pop() {
int value = super.pop();
if (value == min) {
s2.pop();
}
return value;
}
public int min() {
if(s2.isEmpty()) {
return Integer.MAX_VALUE;
} else {
return s2.peek();
}
}
}
Why might this be more space efficient? Suppose we had a very large stack and the first element inserted happened to be the minimum. In the first solution, we would be keeping n integers, where n is the size of the stack. In the second solution though, we store just a few pieces of data: a second stack with one element and the members within this stack.
