Progettare un datastructure per supportare le operazioni di stack e per trovare domande minima

Question

Intervista: Progettare una struttura di dati che ha le seguenti caratteristiche

• spingere i dati
• Pops gli ultimi dati inseriti [LIFO]
• Gives il minimo

Tutte le operazioni di cui sopra dovrebbe avere una complessità di O(1)

Answer 1

Si può fare questo mantenendo due pile

stack - effettuare le normali operazioni di push e pop su questo stack.

minStack - questa pila viene utilizzata per ottenere il minimo in pila nel tempo O(1). In qualsiasi momento l'elemento principale di questa pila sarà il minimo di tutti gli elementi nella 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 

Nella soluzione sopra ogni volta che un elemento viene spinto sulla pila, v'è una corrispondente pressione sul minStack. Quindi in qualsiasi momento il numero di elementi nello stack e minStack sono uguali. Possiamo ottimizzarlo leggermente spingendo un elemento su minStack solo se l'elemento è più piccolo del minimo attuale.

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

Per fare ciò, la struttura dati deve contenere due pile. Si dovrebbe funzionare normalmente; l'altro contiene solo l'ultimo elemento minimo visto. Quando premi un elemento, se è inferiore/uguale al secondo (o lo stack è vuoto), spingilo anche sul secondo stack. Quando schiocchi un elemento, se è uguale alla cima del secondo stack, apri anche il secondo stack.

Il minimo in qualsiasi momento è la parte superiore del secondo stack.

Answer 3

Questa domanda è in realtà chiedendo un Heap

CodaConPriorita è un caso classico (attuazione Heap). Vedi java.util.PriorityQueue

Mi piacerebbe che ci fosse un modo semplice per fare riferimento online al codice sorgente del linguaggio Java dove posso vedere e fare riferimento all'implementazione della classe PriorityQueue.

Answer 4

C'è una soluzione più creativa senza utilizzare uno stack ausiliario.

Supponendo che stiamo per spingere un valore numerico in una pila con numero minimo min. Se il valore è maggiore o uguale allo min, viene inserito direttamente nello stack di dati. Se è inferiore a min, spingiamo 2 * valore - min, e modificare min come valore poiché un nuovo numero minimo viene spinto.

Che ne dici di pop?Lo inseriamo direttamente se la parte superiore dello stack di dati (indicata come top) è maggiore o uguale a min. Altrimenti il ​​numero top non è il vero numero spinto. Il numero reale inserito viene memorizzato come min. Dopo che il numero minimo corrente è spuntato, dobbiamo ripristinare il numero minimo precedente, che è 2 * min - * top *.

Ora dimostriamo la sua correttezza di questa soluzione. Quando il valore è uguale o uguale a min, viene inserito direttamente nello stack di dati senza aggiornare min. Pertanto, quando scopriamo che la parte superiore dello stack di dati è maggiore o uguale a min, possiamo eseguire il pop direttamente senza aggiornare min. Tuttavia, se troviamo il valore è inferiore a min, si preme 2 * valore - * min *. Dovremmo notare che il valore 2 * - * min * è inferiore a valore. Quindi aggiorniamo l'attuale min come valore. Pertanto, la nuova parte superiore dello stack di dati (top) è inferiore all'attuale min. Pertanto, quando scopriamo che la parte superiore dello stack di dati è inferiore a min, il valore reale più alto (numero reale spinto valore) viene memorizzato in min. Dopo aver popolato la parte superiore dello stack di dati, dobbiamo ripristinare il numero minimo precedente. Poiché superiore = valore 2 * -precedente min e valore è corrente min, permeabile min è 2 * corrente min - superiore.

Il C++ codice di esempio è stata di:

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

Questa soluzione è preso in prestito da my blog, e il mio libro "Coding Interviews: Questions, Analysis & Solutions".