Stack com find-min / find-max mais eficiente que O (n)?

Estou interessado em criar uma estrutura de dados Java semelhante a uma pilha que suporte as seguintes operações da forma mais eficiente possível:

  • Push, que adiciona um novo elemento no topo da pilha,
  • Pop, que remove o elemento principal da pilha,
  • Find-Max, que retorna (mas não remove) o maior elemento da pilha, e
  • Find-Min, que retorna (mas não remove) o menor elemento da pilha, e

Qual seria a implementação mais rápida dessa estrutura de dados? Como eu poderia escrever sobre isso em Java?

Esta é uma questão clássica de estruturas de dados. A intuição por trás do problema é a seguinte: a única maneira que o máximo e o mínimo podem mudar é se você empurrar um novo valor para a pilha ou tirar um novo valor da pilha. Sendo assim, suponha que em cada nível da pilha você rastreie os valores máximo e mínimo nesse ponto ou abaixo dele. Então, quando você empurra um novo elemento para a pilha, você pode facilmente (no tempo O (1)) calcular o valor máximo e mínimo em qualquer lugar da pilha, comparando o novo elemento que você acabou de empurrar para o máximo e mínimo atuais. Da mesma forma, quando você soltar um elemento, você irá expor o elemento na pilha um passo abaixo do topo, que já possui os valores máximo e mínimo no restante da pilha armazenada ao lado dele.

Visualmente, suponha que tenhamos uma pilha e adicione os valores 2, 7, 1, 8, 3 e 9, nessa ordem. Começamos empurrando 2, e então empurramos 2 para nossa pilha. Como 2 é agora o maior e menor valor na pilha, registramos isso:

2 (max 2, min 2) 

Agora, vamos empurrar 7. Como 7 é maior que 2 (o atual máximo), acabamos com isso:

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

Observe que agora podemos ler o máximo e o mínimo da pilha olhando para o topo da pilha e vendo que 7 é o máximo e 2 é o mínimo. Se agora empurrarmos 1, obtemos

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

Aqui, sabemos que 1 é o mínimo, já que podemos comparar 1 com o valor mínimo armazenado em cache no topo da pilha (2). Como exercício, certifique-se de entender por que, depois de adicionar 8, 3 e 9, recebemos o seguinte:

  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) 

Agora, se quisermos consultar o max e o min, podemos fazê-lo em O (1) apenas lendo o máximo e o minimo armazenados no topo da pilha (9 e 1, respectivamente).

Agora, suponha que saíssemos do elemento superior. Isso produz 9 e modifica a pilha a 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) 

E agora observe que o máximo desses elementos é 8, exatamente a resposta correta! Se nós, então, empurrarmos 0, teríamos isso:

  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) 

E, como você pode ver, o max e o min são computados corretamente.

No geral, isso leva a uma implementação da pilha que tem O (1) push, pop, find-max e find-min, que é assintoticamente tão boa quanto possível. Vou deixar a implementação como um exercício. 🙂 No entanto, você pode querer considerar a implementação da pilha usando uma das técnicas de implementação de pilha padrão, como o uso de uma matriz dinâmica ou uma lista de objects vinculados , cada qual contendo o elemento stack, min e max. Você pode fazer isso facilmente usando o ArrayList ou o LinkedList . Como alternativa, você poderia usar a class Java Stack fornecida, embora o IIRC tenha alguma sobrecarga devido à synchronization que pode ser desnecessária para esse aplicativo.

Curiosamente, depois de construir uma pilha com essas propriedades, você pode usá-la como um bloco de construção para construir uma fila com as mesmas propriedades e garantias de tempo. Você também pode usá-lo em uma construção mais complexa para construir uma fila com duas extremidades com essas propriedades também.

Espero que isto ajude!

EDIT: Se você está curioso, eu tenho implementações em C ++ de um min-stack e uma fila min- acima mencionada no meu site pessoal. Espero que isso mostre como isso pode parecer na prática!

Embora a resposta esteja certa, mas podemos fazer melhor. Se a pilha tem muitos elementos, então estamos perdendo muito espaço. No entanto, podemos salvar este espaço inútil da seguinte forma:

Em vez de salvar o valor mínimo (ou máximo) em cada elemento, podemos usar duas pilhas. Como a mudança no valor mínimo (ou máximo) não será tão freqüente, nós aumentamos o valor mínimo (ou máximo) para sua respectiva pilha apenas quando o novo valor for <= (ou >= ) para o min atual (ou max) valor.

Aqui está a implementação em 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(); } } } 

Note que usando essa abordagem, teríamos muito poucos elementos em minStack & maxStack , economizando espaço. por exemplo

 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) 

Pode ser tarde demais para responder, mas apenas por uma questão de registro. Aqui está o código 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(); } } 

Classe de pilha:

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

Usando a lista de links:

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