You can implement this by having each node in the stack keep track of the
minimum beneath itself.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;
} 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 large 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;
public StackWithMin2() {
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? If many elements have the same local
min, then we’re keeping a lot of duplicate data.By having the mins kept in a
separate stack, we don’t have this duplicate data (although we do use up a
lot of extra space because we have a stack node instead of a single int).
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
