Стек с find-min / find-max более эффективен, чем O (n)?

Question

Я заинтересован в создании структуры данных Java, аналогичной стеку, который максимально эффективно поддерживает следующие операции:

• Push, который добавляет новый элемент поверх стека,
• Pop, который удаляет верхний элемент стека,
• Find-Max, который возвращает (но не удаляет) самый большой элемент стека, и
• Find-Min, которыйвозвращает (но не удаляет) наименьший элемент стека и

Какая была бы самая быстрая реализация этой структуры данных?Как мне написать его на Java?

Answer 1

Это классический вопрос о структурах данных.Интуиция, лежащая в основе этой проблемы, заключается в следующем: единственный способ изменить максимум и минимум - это вставить новое значение в стек или вытолкнуть новое значение из стека.Учитывая это, предположим, что на каждом уровне в стеке вы отслеживаете максимальные и минимальные значения в или ниже этой точки в стеке.Затем, когда вы помещаете новый элемент в стек, вы можете легко (за время O (1)) вычислить максимальное и минимальное значение в любом месте стека, сравнивая только что добавленный элемент с текущим максимумом и минимумом.Точно так же, когда вы выталкиваете элемент, вы выставляете элемент в стеке на один шаг ниже вершины, который уже имеет максимальные и минимальные значения в оставшейся части стека, хранящейся рядом с ним.

Визуальночто у нас есть стек и добавляем значения 2, 7, 1, 8, 3 и 9 в указанном порядке.Мы начинаем с нажатия 2, и поэтому мы помещаем 2 в наш стек.Поскольку 2 теперь является самым большим и наименьшим значением в стеке, мы записываем это:

 2  (max 2, min 2)

Теперь давайте нажмем 7. Так как 7 больше 2 (текущий максимум), мы получаемthis:

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

Обратите внимание, что прямо сейчас мы можем считывать максимум и минимум стека, посмотрев на вершину стека и увидев, что 7 - это максимум, а 2 - это минимум.Если мы теперь нажмем 1, мы получим

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

Здесь мы знаем, что 1 - это минимум, поскольку мы можем сравнить 1 с кэшированным минимальным значением, хранящимся в стеке (2).В качестве упражнения убедитесь, что вы понимаете, почему после добавления 8, 3 и 9 мы получаем следующее:

 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)

Теперь, если мы хотим запросить max и min, мы можем сделать это в O (1) просто считывая сохраненные значения max и min над стеком (9 и 1 соответственно).

Теперь предположим, что мы выскакиваем из верхнего элемента.Это дает 9 и изменяет стек так:

 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)

И теперь обратите внимание, что максимум этих элементов равно 8, точно правильный ответ!Если мы затем нажмем 0, мы получим это:

 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)

И, как вы можете видеть, макс и мин вычисляются правильно.

В целом, это приводит к реализациистек, который имеет O (1) push, pop, find-max и find-min, что асимптотически так же хорошо, как и получается.Я оставлю реализацию в качестве упражнения.:-) Однако вы можете рассмотреть возможность реализации стека с использованием одного из стандартных методов реализации стека, таких как использование динамического массива или связанного списка объектов, каждый из которых содержитэлемент стека, мин и макс.Вы можете сделать это легко, используя ArrayList или LinkedList.В качестве альтернативы вы можете использовать предоставленный класс Java Stack, хотя IIRC имеет некоторые накладные расходы из-за синхронизации, которая может быть ненужной для этого приложения.

Интересно, что после того, как вы создали стек с этими свойствами, выможет использовать его как строительный блок для построения очереди с такими же свойствами и гарантиями времени.Вы также можете использовать его в более сложной конструкции для создания двусторонней очереди с этими свойствами.

Надеюсь, это поможет!

РЕДАКТИРОВАТЬ: Если вы 'любопытно, у меня есть C ++ реализации минимальный стек и вышеупомянутая минимальная очередь на моем личном сайте.Надеюсь, это показывает, как это может выглядеть на практике!

Answer 2

Хотя ответ верен, но мы можем добиться большего. Если в стеке много элементов, то мы тратим много места. Тем не менее, мы можем сохранить это бесполезное пространство следующим образом:

Вместо сохранения минимального (или максимального) значения для каждого элемента мы можем использовать два стека. Поскольку изменение минимального (или максимального) значения не будет таким частым, мы помещаем минимальное (или максимальное) значение в соответствующий стек только тогда, когда новое значение равно <= (или >=) до текущего минимума (или max) значение.

Вот реализация в 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();
        }
    }
}

Обратите внимание, что при таком подходе у нас будет очень мало элементов в minStack & maxStack, что позволит сэкономить место. например,

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 3

Может быть слишком поздно, чтобы ответить, но только ради записи. Вот код 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();

    }
}

Класс стека:

class Node {

        int data;
        int min;
        int max;

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

        public Node() {
            super();
        }
    }

Answer 4

Использование 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;
    }
}