Si puede dejar que pop () / push () sea más lento que O (1), puede tener un O (1) popMin. Por ejemplo, puede mantener una pila auxiliar ordenada y agregar un solo bit “reventado” a cada elemento de almacenamiento. popMin elimina el elemento de la pila auxiliar que tiene un puntero al elemento normal de la pila, lo marca como “reventado”. Eso es O (1). El estallido normal necesita hacer estallar elementos hasta que encuentre uno que no esté marcado como reventado (y tal vez pueda argumentar que eso es tiempo constante amortizado, pero no creo que realmente lo sea).
O … puede usar una lista doblemente vinculada para organizar su pila y mantener una pila auxiliar con punteros en la pila “real”. popMin puede desvincular el elemento en la pila “real” que aparece. O (1), y el pop normal se mantendría O (1) … excepto que tiene que actualizar la pila auxiliar. Sin embargo, puede usar la misma técnica, hacer que la pila auxiliar también sea una lista doblemente vinculada.
Empujar sigue siendo costoso porque necesitas llevarlo al lugar correcto en la pila auxiliar …
- Cómo habilitar la compresión gzip
- ¿Cómo encuentras la distancia entre dos lugares, sin usar los mapas de Google?
- ¿Cómo crean los algoritmos los programadores de software?
- ¿Qué es exactamente el algoritmo?
- ¿Qué algoritmos debo saber para desarrollar una aplicación web sin conexión primero?
Sin embargo, espero no haber hecho tu tarea.
