java - ¿Apilar con find-min/find-max es más eficiente que O(n)?

max integer java 8

Question

Estoy interesado en crear una estructura de datos Java similar a una pila que soporte las siguientes operaciones de la manera más eficiente posible:

• Push, que agrega un nuevo elemento sobre la pila,
• Pop, que elimina el elemento superior de la pila,
• Find-Max, que devuelve (pero no elimina) el elemento más grande de la pila, y
• Find-Min, que devuelve (pero no elimina) el elemento más pequeño de la pila, y

¿Cuál sería la implementación más rápida de esta estructura de datos? ¿Cómo podría escribir sobre Java?

Answer 1

Aunque la answer es correcta, pero podemos hacerlo mejor. Si la pila tiene muchos elementos, estamos desperdiciando mucho espacio. Sin embargo, podemos guardar este espacio inútil de la siguiente manera:

En lugar de guardar el valor mínimo (o máximo) con cada elemento, podemos usar dos pilas. Debido a que el cambio en el valor mínimo (o máximo) no será tan frecuente, aplicamos el valor mínimo (o máximo) a su pila respectiva solo cuando el nuevo valor es <= (o >= ) al mínimo actual (o máximo) valor.

Aquí está la implementación en Java :

public class StackWithMinMax extends Stack<Integer> {
private Stack<Integer> minStack;
private Stack<Integer> maxStack;
public StackWithMinMax () {
minStack = new Stack<Integer>();
maxStack = new Stack<Integer>();
}
public void push(int value){
if (value <= min()) { // Note the ''='' sign here
minStack.push(value);
}
if (value >= max()) {
maxStack.push(value);
}
super.push(value);
}
public Integer pop() {
int value = super.pop();
if (value == min()) {
minStack.pop();
}
if (value == max()) {
maxStack.pop();
}
return value;
}
public int min() {
if (minStack.isEmpty()) {
return Integer.MAX_VALUE;
} else {
return minStack.peek();
}
}
public int max() {
if (maxStack.isEmpty()) {
return Integer.MIN_VALUE;
} else {
return maxStack.peek();
}
}
}

Tenga en cuenta que al usar este enfoque, tendríamos muy pocos elementos en minStack & maxStack , ahorrando espacio. p.ej

Stack : MinStack : MaxStack
7 7 7
4 4 7
5 1 8 (TOP)
6 1 (TOP)
7
8
1
1
7
2
4
2 (TOP)

Answer 2

Esta es una pregunta clásica sobre estructuras de datos. La intuición detrás del problema es la siguiente: la única forma en que el máximo y el mínimo pueden cambiar es si inserta un nuevo valor en la pila o saca un nuevo valor de la pila. Dado esto, supongamos que en cada nivel de la pila se hace un seguimiento de los valores máximos y mínimos en o debajo de ese punto en la pila. Luego, cuando inserta un nuevo elemento en la pila, puede calcular fácilmente (en tiempo O (1)) el valor máximo y mínimo en cualquier lugar de la pila comparando el nuevo elemento que acaba de presionar con el máximo y el mínimo actuales. De manera similar, cuando extrae un elemento, expondrá el elemento en la pila un paso por debajo de la parte superior, que ya tiene los valores máximo y mínimo en el resto de la pila almacenada a su lado.

Visualmente, supongamos que tenemos una pila y agregue los valores 2, 7, 1, 8, 3 y 9, en ese orden. Comenzamos presionando 2, por lo que presionamos 2 en nuestra pila. Como 2 ahora es el valor más grande y más pequeño en la pila, registramos esto:

 2 (max 2, min 2)

Ahora, presionemos 7. Como 7 es mayor que 2 (el máximo actual), terminamos con esto:

 7 (max 7, min 2)
2 (max 2, min 2)

Tenga en cuenta que en este momento podemos leer el máximo y el mínimo de la pila mirando la parte superior de la pila y viendo que 7 es el máximo y 2 es el mínimo. Si ahora presionamos 1, obtenemos

 1 (max 7, min 1)
7 (max 7, min 2)
2 (max 2, min 2)

Aquí, sabemos que 1 es el mínimo, ya que podemos comparar 1 con el valor mínimo en caché almacenado encima de la pila (2). Como ejercicio, asegúrese de entender por qué después de agregar 8, 3 y 9, obtenemos esto:

 9 (max 9, min 1)
3 (max 8, min 1)
8 (max 8, min 1)
1 (max 7, min 1)
7 (max 7, min 2)
2 (max 2, min 2)

Ahora, si queremos consultar el máximo y el mínimo, podemos hacerlo en O (1) simplemente leyendo los máximos y mínimos almacenados encima de la pila (9 y 1, respectivamente).

Ahora, supongamos que sacamos el elemento superior. Esto produce 9 y modifica la pila para ser

 3 (max 8, min 1)
8 (max 8, min 1)
1 (max 7, min 1)
7 (max 7, min 2)
2 (max 2, min 2)

Y ahora observe que el máximo de estos elementos es 8, ¡exactamente la respuesta correcta! Si presionamos 0, obtendríamos esto:

 0 (max 8, min 0)
3 (max 8, min 1)
8 (max 8, min 1)
1 (max 7, min 1)
7 (max 7, min 2)
2 (max 2, min 2)

Y, como puede ver, el máximo y el mínimo se calculan correctamente.

En general, esto conduce a una implementación de la pila que tiene O (1) push, pop, find-max y find-min, que es tan asintóticamente tan buena como se puede obtener. Dejaré la implementación como un ejercicio. :-) Sin embargo, es posible que desee considerar la implementación de la pila utilizando una de las técnicas de implementación de pila estándar, como el uso de una matriz dinámica o una lista de objetos vinculados , cada uno de los cuales contiene el elemento de pila, mínimo y máximo. Puede hacerlo fácilmente sacando ArrayList de ArrayList o LinkedList . Alternativamente, puede usar la clase Java Stack proporcionada, aunque IIRC tiene algunos gastos generales debido a la sincronización que podría ser innecesaria para esta aplicación.

Curiosamente, una vez que haya construido una pila con estas propiedades, puede usarla como un bloque de construcción para construir una cola con las mismas propiedades y garantías de tiempo. También puede usarlo en una construcción más compleja para construir una cola de doble extremo con estas propiedades también.

¡Espero que esto ayude!

EDITAR: Si eres curioso, tengo implementaciones en C ++ de un min-stack y una min-queue antes mencionada en mi sitio personal. ¡Con suerte, esto muestra lo que esto podría parecer en la práctica!

Answer 3

Puede que sea demasiado tarde para responder, pero solo por el hecho de estar registrado. Aquí está el código de Java.

import java.util.ArrayList;
import java.util.List;
public class MinStack {
List<Node> items;
public void push(int num) {
if (items == null) {
items = new ArrayList<Node>();
}
Node node = new Node(num);
if (items.size() > 0) {
node.min = Math.min(items.get(items.size() - 1).min, num);
node.max = Math.max(items.get(items.size() - 1).max, num);
} else {
node.min = num;
node.max = num;
}
items.add(node);
printStack();
}
public Node pop() {
Node popThis = null;
if (items != null && items.size() > 0) {
popThis = this.items.get(items.size() - 1);
items.remove(items.size() - 1);
}
printStack();
return popThis;
}
public int getMin() {
if (items != null && items.size() > 0) {
int min = this.items.get(items.size() - 1).min;
System.out.println("Minimum Element > " + min);
return min;
}
return -1;
}
public int getMax() {
if (items != null && items.size() > 0) {
int max = this.items.get(items.size() - 1).max;
System.out.println("Maximum Element > " + max);
return max;
}
return -1;
}
public void printStack() {
int i = 0;
for (Node n : items) {
System.out.print(n.data + " > ");
if (i == items.size() - 1) {
System.out.print(" | Min = " + n.min + " |");
System.out.print(" | Max = " + n.max + " |");
}
i++;
}
System.out.println();
}
public static void main(String args[]) {
MinStack stack = new MinStack();
stack.push(10);
stack.push(13);
stack.push(19);
stack.push(3);
stack.push(2);
stack.push(2);
stack.printStack();
stack.pop();
//stack.getMin();
stack.printStack();
}
}

Clase de pila:

class Node {
int data;
int min;
int max;
public Node(int data) {
super();
this.data = data;
}
public Node() {
super();
}
}

Answer 4

Usando Linkedlist:

public class MaxMinStack {
MaxMinLLNode headMin = null;
MaxMinLLNode headMax = null;
MaxMinLLNode tailMin = null;
MaxMinLLNode tailMax = null;
public void push(int data) {
MaxMinLLNode node = new MaxMinLLNode(data, null);
if (headMin == null) {
headMin = node;
tailMin = node;
} else {
if (data < headMin.data) {
tailMin = headMin;
headMin = node;
node.nextNodeReference = tailMin;
}
}
if (headMax == null) {
headMax = node;
tailMax = node;
} else {
if (data > headMax.data) {
tailMax = headMax;
headMax = node;
node.nextNodeReference = tailMax;
}
}
}
public void pop() {
System.out.println("Max Element:" + " " + String.valueOf(headMax.data));
System.out.println("Min Element:" + " " + String.valueOf(headMin.data));
}
public void traverse() {
MaxMinLLNode ptrMin = headMin;
MaxMinLLNode ptrMax = headMax;
System.out.println("Min");
while (ptrMin != null) {
System.out.println(ptrMin.data);
ptrMin = ptrMin.nextNodeReference;
}
System.out.println("Max");
while (ptrMax != null) {
System.out.println(ptrMax.data);
ptrMax = ptrMax.nextNodeReference;
}
}
public static void main(String[] args) {
MaxMinStack m = new MaxMinStack();
m.push(7);
m.push(4);
m.push(5);
m.push(6);
m.push(7);
m.push(8);
m.push(1);
m.push(1);
m.push(7);
m.push(2);
m.push(4);
m.push(2);
m.traverse();
m.pop();
}
}
class MaxMinLLNode {
int data;
MaxMinLLNode nextNodeReference;
MaxMinLLNode(int data, MaxMinLLNode node) {
this.data = data;
this.nextNodeReference = node;
}
}