conception une structure de données pour soutenir les opérations de la pile et de trouver au minimum

Question

Interview question: Concevoir une structure de données qui présente les caractéristiques suivantes

• pousser les données
• POPS les dernières données insérées [LIFO]
• Donne le minimum

Toutes les opérations ci-dessus devraient avoir une complexité de O(1)

Answer 1

Vous pouvez le faire en maintenant deux piles

stack - faire les opérations habituelles push et pop sur cette pile.

minStack - cette pile est utilisée pour obtenir le min ele dans la pile en O(1). À tout moment, l'élément supérieur de cette pile sera le min de tous les éléments de la pile.

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 

Dans la solution ci-dessus à chaque fois un élément est poussé sur la pile, il y a une poussée correspondante sur minStack. Donc, à tout moment, le nombre d'éléments dans la pile et minStack sont identiques. Nous pouvons légèrement l'optimiser en poussant un élément sur minStack seulement si l'élément est plus petit que le min.

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

Pour ce faire, votre structure de données doit contenir deux piles. On devrait fonctionner normalement. l'autre ne contient que le dernier élément minimum vu. Lorsque vous poussez un élément, s'il est inférieur/égal au sommet de la deuxième pile (ou que la pile est vide), appuyez également sur la deuxième pile. Lorsque vous sautez un élément, s'il est égal au sommet de la deuxième pile, sautez aussi la deuxième pile.

Le minimum à tout moment est le haut de la deuxième pile.

Answer 3

Cette question demande en fait une Heap

PriorityQueue est un cas classique (mise en œuvre de Heap). Voir java.util.PriorityQueue

Je souhaite qu'il y avait un moyen facile en ligne pour faire référence au code source du langage Java où je peux voir et se référer à l'implémentation de la classe PriorityQueue.

Answer 4

Il existe une solution plus créative sans utiliser de pile auxiliaire.

Supposant que nous allons pousser un certain nombre valeur dans une pile avec un nombre minimum min. Si la valeur est supérieure ou égale à min, elle est poussée directement dans la pile de données. Si elle est inférieure à min, nous poussons 2 * valeur-min et mettre à jour min comme valeur depuis un nouveau minimum est poussé.

Que diriez-vous de pop?Nous le sautons directement si le sommet de la pile de données (noté top) est supérieur ou égal à min. Sinon, le numéro top n'est pas le nombre réellement poussé. Le vrai nombre poussé est stocké sous min. Après que le nombre minimum actuel est sorti, nous devons restaurer le nombre minimum précédent, qui est 2 * min - * top *.

Maintenant, nous allons démontrer son exactitude de cette solution. Lorsque valeur est supérieure ou égale à min, il est poussé dans la pile de données directe sans mettre à jour min. Par conséquent, lorsque nous constatons que le sommet de la pile de données est supérieur ou égal à min, nous pouvons afficher directement sans mettre à jour min. Cependant, si nous trouvons valeur est moins alors min, nous poussons 2 * valeur - * min *. Nous devrions remarquer que la valeur 2 * - * min * est inférieure à valeur. Ensuite, nous mettons à jour le courant min comme valeur. Par conséquent, le nouveau sommet de la pile de données (top) est inférieur à l'actuel min. Par conséquent, lorsque nous constatons que le sommet de la pile de données est inférieur à min, le réel supérieur (réel poussé numéro valeur) est stocké dans min. Après avoir déplacé le haut de la pile de données, nous devons restaurer le nombre minimum précédent. Depuis haut = 2 * valeur -Précédent min et valeur est en cours min, min drainant est 2 * Courant min-top.

code exemple du C est indiqué ci-dessous:

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; 
} 

Cette solution est empruntée à my blog, et mon livre "Coding Interviews: Questions, Analysis & Solutions".