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

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

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

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

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 stack o saca un nuevo valor de la stack. Dado esto, supongamos que en cada nivel de la stack se hace un seguimiento de los valores máximos y mínimos en o debajo de ese punto en la stack. Luego, cuando inserta un nuevo elemento en la stack, puede calcular fácilmente (en tiempo O (1)) el valor máximo y mínimo en cualquier lugar de la stack 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 stack un paso por debajo de la parte superior, que ya tiene los valores máximo y mínimo en el rest de la stack almacenada a su lado.

Visualmente, supongamos que tenemos una stack y agregue los valores 2, 7, 1, 8, 3 y 9, en ese orden. Comenzamos presionando 2, por lo que presionamos 2 en nuestra stack. Como 2 ahora es el valor más grande y más pequeño en la stack, 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 stack mirando la parte superior de la stack 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 stack (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 stack (9 y 1, respectivamente).

Ahora, supongamos que sacamos el elemento superior. Esto produce 9 y modifica la stack 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 stack 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 stack utilizando una de las técnicas de implementación de stack 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 stack, 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 stack 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!

Aunque la respuesta es correcta, pero podemos hacerlo mejor. Si la stack 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 stacks. 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 stack 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 { private Stack minStack; private Stack maxStack; public StackWithMinMax () { minStack = new Stack(); maxStack = new Stack(); } 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) 

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 items; public void push(int num) { if (items == null) { items = new ArrayList(); } 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 stack:

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

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