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

Ответ 1

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

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

 2  (max 2, min 2)

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

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

Обратите внимание, что прямо сейчас мы можем прочитать max и min стека, посмотрев на верхнюю часть стека и увидев, что 7 - max, а 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)

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

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

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

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

EDIT: Если вам интересно, у меня есть реализации С++ min-stack и вышеупомянутый min-queue на моем личном сайте. Надеюсь, это показывает, как это может выглядеть на практике!

Ответ 2

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

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

Ответ 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();
        }
    }

Ответ 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;
    }
}