@Teja: If I insert numbers in decreasing order, your solution will use much more memory than just including the min in the same stack. Also, what happens if I push the same minimum value several times? In your solution, when the first one is popped off, that minimum value is thrown out even though that value is still in the stack. For instance: Push: 20 1 3 1 8 1 10 1 12 1 Pop Min() will now return 20, even though 20 is the largest item in the stack.
Don On Sep 5, 11:49 am, teja bala <[email protected]> wrote: > 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.
