Diseño de una estructura de datos para apoyar operaciones de la pila y para encontrar mínimo pregunta

Question

Entrevista: Diseñar una estructura de datos que tiene las siguientes características

• empuje los datos
• POPS los últimos datos insertados [LIFO]
• Da la mínima

Todas las operaciones anteriores deben tener una complejidad de O(1)

Answer 1

Usted puede hacer esto mediante el mantenimiento de dos pilas

stack - hacer las operaciones de inserción y extracción habituales en esta pila.

minStack - esta pila se usa para obtener el elemento ele en la pila en O(1) tiempo. En cualquier punto, el elemento superior de esta pila será el mínimo de todos los elementos en la pila.

push(item a) 
    // push the element on the stack. 
    stack.push(a) 

    // find the min of the ele to be pushed and the ele on top of minStack. 
    if(minStack.isEmpty()) 
     min = a 
    else 
     min = Min(a,minStack.top()) 

    // push the min ele on the minStack. 
    minStack.push(min) 
end push 


pop() 
    // pop and discard 
    minStack.pop() 

    // pop and return 
    return stack.pop() 
end pop 


findMin() 
    return minStack.top() 
end findMin 

En la solución anterior cada vez que un elemento se empuja en la pila, hay un empuje correspondiente en minStack. Entonces, en cualquier momento, la cantidad de elementos en stack y minStack es la misma. Podemos optimizarlo ligeramente presionando un elemento en minStack solo si el elemento es más pequeño que el presente mín.

push(item a) 
    // push the element on the orginal stack. 
    stack.push(a) 

    if(minStack.isEmpty()) 
      // if minStack is empty push. 
      minStack.push(a) 
    // else push only if the element is less than or equal to the present min. 
    else if(a <= minStack.top()) 
     minStack.push(a) 
end push 

pop() 
    // pop from the stack 
    ele = stack.top()  
    if(minStack.top() == ele) 
      // pop only if the top element is ele. 
     minStack.pop() 

    // return the popped element. 
    return ele 
end pop 

Answer 2

Para hacer esto, su estructura de datos debe contener dos pilas. Uno debe funcionar como normal; el otro solo contiene el último elemento mínimo visto. Cuando presionas un elemento, si es menor o igual que la parte superior de la segunda pila (o la pila está vacía), empújala también en la segunda pila. Cuando sacas un elemento, si es igual a la parte superior de la segunda pila, también sacas la segunda pila.

El mínimo en cualquier momento es la parte superior de la segunda pila.

Answer 3

Esta pregunta es en realidad pidiendo un PriorityQueue Heap

es un caso clásico (aplicación de Heap). Ver java.util.PriorityQueue

Ojalá hubiera una manera fácil en línea para hacer referencia al código fuente del lenguaje Java donde puedo ver y referirme a la implementación de la clase PriorityQueue.

Answer 4

Hay una solución más creativa sin utilizar una pila auxiliar.

Suponiendo que vamos a empujar un valor numérico en una pila con el número mínimo min. Si valor es mayor o igual que min, se envía directamente a la pila de datos. Si es menos de min, empujamos 2 * valor - min, y actualizamos min como valor ya se empuja un nuevo número mínimo.

¿Qué tal pop?Lo mostramos directamente si la parte superior de la pila de datos (se denota como arriba) es mayor o igual que min. De lo contrario, el número arriba no es el número real empujado. El número real empujado se almacena como min. Después de que aparezca el número mínimo actual, debemos restablecer el número mínimo anterior, que es 2 * mínimo - * arriba *.

Ahora demos la corrección de esta solución. Cuando valor es igual o mayor que min, se empuja directamente a la pila de datos sin actualizar min. Por lo tanto, cuando encontramos que la parte superior de la pila de datos es mayor o igual que min, podemos abrir directamente sin actualizar min. Sin embargo, si encontramos valor es menor que min, pulsamos 2 * valor - * min *. Deberíamos notar que 2 * valor - * min * es menor que valor. Luego actualizamos el mínimo como valor. Por lo tanto, la nueva parte superior de la pila de datos (arriba) es menor que la actual min. Por lo tanto, cuando descubrimos que la parte superior de la pila de datos es menor que min, la parte superior real (número real empujado valor) se almacena en min. Después de abrir la parte superior de la pila de datos, debemos restaurar el número mínimo anterior. Desde superior = 2 * valor -Anterior min y valor es actual min, permeable min es 2 * actual min-superior.

El C++ código de ejemplo se muestra a continuación:

template <typename T> class StackWithMin { 
public: 
    StackWithMin(void) {} 
    virtual ~StackWithMin(void) {} 

    T& top(void); 
    void push(const T& value); 
    void pop(void); 
    const T& min(void) const; 

private: 
    std::stack<T> m_data;  // data stack, to store numbers 
    T    m_min;  // minimum number 
}; 

template <typename T> void StackWithMin<T>::push(const T& value) { 
    if(m_data.size() == 0) { 
     m_data.push(value); 
     m_min = value; 
    } 
    else if(value >= m_min) { 
     m_data.push(value); 
    } 
    else { 
     m_data.push(2 * value - m_min); 
     m_min = value; 
    } 
} 

template <typename T> void StackWithMin<T>::pop() { 
    assert(m_data.size() > 0); 

    if(m_data.top() < m_min) 
     m_min = 2 * m_min - m_data.top(); 

    m_data.pop(); 
} 

template <typename T> const T& StackWithMin<T>::min() const { 
    assert(m_data.size() > 0); 

    return m_min; 
} 

template <typename T> T& StackWithMin<T>::top() { 
    T top = m_data.top(); 
    if(top < m_min) 
     top = m_min; 

    return top; 
} 

Esta solución ha sido tomada de my blog, y mi libro "Coding Interviews: Questions, Analysis & Solutions".