Вставить, удалить, max в O (1)

Ответ 1

Это классический вопрос интервью и обычно представлен следующим образом:

Создайте структуру данных, подобную стеку, которая выполняет операции push, pop и min (или max) в O (1) раз. Нет ограничений по пространству.

Ответ: вы используете два стека: основной стек и минимальный (или максимальный) стек.

Итак, например, после нажатия 1,2,3,4,5 на стек ваши стеки будут выглядеть так:

MAIN   MIN
+---+  +---+
| 5 |  | 1 |
| 4 |  | 1 |
| 3 |  | 1 |
| 2 |  | 1 |
| 1 |  | 1 |
+---+  +---+

Однако, если вы должны были нажать 5,4,3,2,1, стеки выглядели бы так:

MAIN   MIN
+---+  +---+
| 1 |  | 1 |
| 2 |  | 2 |
| 3 |  | 3 |
| 4 |  | 4 |
| 5 |  | 5 |
+---+  +---+

Для 5,2,4,3,1 у вас будет:

MAIN   MIN
+---+  +---+
| 1 |  | 1 |
| 3 |  | 2 |
| 4 |  | 2 |
| 2 |  | 2 |
| 5 |  | 5 |
+---+  +---+

и т.д.

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

Ответ 2

Комментарий @KennyTM указывает важную недостающую деталь - вставьте туда и удалите откуда. Поэтому я собираюсь предположить, что вы всегда хотите вставлять и удалять только с одного конца, как стек.

Вставка (push) и Delete (pop) - O (1).

Чтобы получить Max в O (1), используйте дополнительный стек для записи текущего max, который соответствует основному стеку.

Ответ 3

В следующем решении используется O (1) дополнительная память и O (1) время для операций max, push и pop. Сохраняйте переменную max, которая будет отслеживать текущий максимальный элемент в любое конкретное время. Давайте используем тот факт, что при обновлении max все элементы в стеке должны быть меньше, чем новый max-элемент. Когда происходит операция push и новый элемент (newElement) больше текущего max, мы нажимаем max + newElement в стеке и обновляем max = newElement.

Когда мы делаем операцию pop, и мы обнаруживаем, что текущий popped элемент больше текущего max, тогда мы знаем, что это место, где мы обновили наш стек, чтобы удерживать max + elem. Таким образом, фактический элемент, который нужно вернуть, - max и max = poppedElem - max.

Например, если мы нажимаем 1, 2, 3, 4, 5, то стек и максимальная переменная будут выглядеть следующим образом:

MAIN       Value of MAX
+---+      +---+
| 9 |      max = | 5 |
| 7 |      max = | 4 |
| 5 |      max = | 3 |
| 3 |      max = | 2 |
| 1 |      max = | 1 |
+---+      +---+

Теперь давайте скажем, что мы выталкиваем элемент, мы будем в основном pop, max element (начиная с top > max) и обновляем максимальный элемент до (top-max)

MAIN       Value of MAX
+---+      +---+
| 7 |      max = | 4 | = (9-5)
| 5 |      max = | 3 |
| 3 |      max = | 2 |
| 1 |      max = | 1 |
+---+      +---+

Теперь скажем, что мы нажимаем числа 5, 4, 3, 2, 1, стек будет выглядеть так:

MAIN       Value of MAX
+---+      +---+
| 1 |      max = | 5 |
| 2 |      max = | 5 |
| 3 |      max = | 5 |
| 4 |      max = | 5 |
| 5 |      max = | 5 |
+---+      +---+

Когда мы выходим, верхняя часть стека складывается, так как top < max и max остается неизменным.

Ниже приведен псевдокод для каждой операции для лучшего понимания.

Elem max;
void Push(Elem x){
    if x < max :
        push(x);
    else{
        push(x+max);
        max = x;
    }
}
Elem Pop(){
    Elem p = pop();
    if |p| < |max|:
        return p;
    else{
        max = p - max;
        return max;
    }
}
Elem Max(){
    return max;
}

push и pop - обычные операции стека. Надеюсь, это поможет.

Ответ 4

Если вы используете только сравнения, вам будет трудно найти такую ​​структуру данных.

Например, вы могли бы вставить n элементов, get max, delete max и т.д. и могли сортировать числа в O (n) времени, тогда как теоретическая нижняя граница - Omega (nlogn).

Ответ 5

Хотя @Can Berk Güder answer прав. Но если у нас есть пространственное ограничение, мы можем сделать намного лучше, даже если элементы не различны. Для получения дополнительной информации см. Мой ответ здесь с реализацией в Java.

Ответ 6

Ниже программа отслеживает максимальные элементы в стеке таким образом, что в любой момент времени верхний указатель дает нам максимум в стеке: Таким образом, max будет O (1), и мы можем найти max max [N]

ITEM   MAX

+---+  +---+
| 1 |  | 1 |
| 10|  | 10|
| 9 |  | 10|
| 19|  | 19| <--top
+---+  +---+

Программа Java:

public class StackWithMax {

private int[] item;
private int N = 0;
private int[] max;

public StackWithMax(int capacity){
    item = new int[capacity];//generic array creation not allowed
    max = new int[capacity];
}

public void push(int item){
    this.item[N++] = item;
    if(max[N-1] > item) {
        max[N] = max[N-1];
    } else {
        max[N] = item;
    }
}

public void pop() {
    this.item[N] = 0;
    this.max[N] = 0;
    N--;
}

public int findMax(){
    return this.max[N];
}
public static void main(String[] args) {
    StackWithMax max = new StackWithMax(10);
    max.push(1);
    max.push(10);
    max.push(9);
    max.push(19);
    System.out.println(max.findMax());
    max.pop();
    System.out.println(max.findMax());


}

}

Ответ 7

Как уже отмечалось, в вопросе отсутствует какая-то информация. Вы не указываете, нужно ли вставлять/удалять, а также характер данных, с которыми мы имеем дело.

Некоторые идеи, которые могут быть полезны: вы говорите,

Вставить/удалить/максимальную операцию в O (1)

заметим, что если мы можем вставить, удалить и найти maximun в O (1), то мы можем использовать эту хипотехническую технику для сортировки в O (n), потому что мы можем вставить n элементов, а затем взять max/delete и мы все сортируем. Было доказано, что ни один алгоритм сортировки, основанный на сравнениях, не может сортировать меньше, чем O (nlogn), поэтому мы знаем, что никакой подход, основанный на сравнении, не будет работать. На самом деле одним из самых быстрых способов сделать это является очередь Brodal, но время ее удаления превышает O (1).

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

Но, возможно, это было не что-то общее. Другая интерпретация заключается в том, что вставка/удаление - это классический стек. В этом ограниченном случае вы можете использовать двойной стек, который Can Berk Güder дал вам.

Ответ 8

Хэш-таблица может поддерживать вставку/удаление в O (1), но не знает о максимуме. Вам, вероятно, придется как-то следить за этим.