Diseñe una pila que admita push, pop, top y recuperación del elemento mínimo en un tiempo constante.
push (x): empuja el elemento x hacia la pila.
pop (): elimina el elemento en la parte superior de la pila.
top (): obtiene el elemento superior.
getMin (): recupera el elemento mínimo de la pila.
Solución Java
Para hacer un tiempo constante de getMin (), necesitamos realizar un seguimiento del elemento mínimo para cada elemento en la pila. Defina una clase de elemento que contenga el valor del elemento, el valor mínimo y el puntero a los elementos que se encuentran debajo.
class Elem{ public int value; public int min; public Elem next; public Elem(int value, int min){ this.value = value; this.min = min; } } public class MinStack { public Elem top; /** initialize your data structure here. */ public MinStack() { } public void push(int x) { if(top == null){ top = new Elem(x, x); }else{ Elem e = new Elem(x, Math.min(x,top.min)); e.next = top; top = e; } } public void pop() { if(top == null) return; Elem temp = top.next; top.next = null; top = temp; } public int top() { if(top == null) return -1; return top.value; } public int getMin() { if(top == null) return -1; return top.min; } } |
