Создайте динамический стек, используя массивы, которые поддерживают getMin() за время O(1) и дополнительное пространство O(1).
Опубликовано: 1 Сентября, 2022
Разработайте специальный динамический стек с использованием массива, который поддерживает все операции стека, такие как push() , pop() , peek() , isEmpty() и getMin() с постоянной сложностью времени и пространства.
Примеры:
Assuming the right to left orientation as the top to bottom orientation and performing the operations:
- Push(10): 10 is added to the top of the stack. Thereafter, the stack modifies to {10}.
- Push(4): 4 is added to the top of the stack. Thereafter, the stack modifies to {10, 4}.
- Push(9): 9 is added to the top of the stack. Thereafter, the stack modifies to {10, 4, 9}.
- Push(6): 6 is added to the top of the stack. Thereafter, the stack modifies to {10, 4, 9, 6}.
- Push(5): 5 is added to the top of the stack. Thereafter, the stack modifies to {10, 4, 9, 6, 5}.
- Peek(): Prints the top element of the stack 5.
- getMin(): Prints the minimum element of the stack 4.
- Pop(): Deletes the top most element, 5 from the stack. Thereafter, the stack modifies to {10, 4, 9, 6}.
- Pop(): Deletes the top most element, 6 from the stack. Thereafter, the stack modifies to {10, 4, 9}.
- Pop(): Deletes the top most element, 9 from the stack. Thereafter, the stack modifies to {10, 4}.
- Pop(): Deletes the top most element, 4 from the stack. Thereafter, the stack modifies to {10}.
- Peek(): Prints the top element of the stack 10.
- getMin(): Prints the minimum element of the stack 10.
Подход: для реализации динамического стека с использованием массива идея состоит в том, чтобы удваивать размер массива каждый раз, когда массив заполняется. Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте массив, скажем, arr[] с начальным размером 5 , чтобы реализовать стек.
- Кроме того, инициализируйте две переменные, скажем, top и minEle , для хранения индекса верхнего элемента стека и минимального элемента стека.
- Теперь выполните следующие операции со стеком:
- isEmpty(): проверяет, пуст стек или нет.
- Возвращает true, если top меньше или равен 0 . В противном случае вернуть ложь.
- Push(x): вставляет x на вершину стека.
- Если стек пуст, вставьте x в стек и сделайте minEle равным x .
- Если стек не пуст, сравните x с minEle . Возникают два случая:
- Если x больше или равен minEle , просто вставьте x .
- Если x меньше minEle , вставьте (2*x – minEle) в стек и сделайте minEle равным x .
- Если используемый массив заполнен, удвойте размер массива, а затем скопируйте все элементы предыдущего массива в новый массив, а затем назначьте адрес нового массива исходному массиву. После этого выполните операцию push, как описано выше.
- Pop(): удаляет элемент из вершины стека.
- Пусть удаленный элемент будет y . возникают два случая
- Если y больше или равно minEle , минимальный элемент в стеке по-прежнему остается minEle .
- Если y меньше minEle , минимальный элемент теперь становится (2*minEle – y) , поэтому обновите minEle как minEle = 2*minEle-y .
- getMin(): находит минимальное значение стека.
- Если стек не пуст, верните значение minEle . В противном случае верните « -1 » и напечатайте « Underflow ».
- isEmpty(): проверяет, пуст стек или нет.
Иллюстрация:
Нажмите (х)
- Число для вставки: 3, стек пуст, поэтому вставьте 3 в стек и minEle = 3.
- Вставляемое число: 5, стек не пуст, 5> minEle, вставьте 5 в стек и minEle = 3.
- Вставляемое число: 2, стек не пуст, 2< minEle, вставьте (2*2-3 = 1) в стек и minEle = 2.
- Вставляемое число: 1, стек не пуст, 1< minEle, вставить (2*1-2 = 0) в стек и minEle = 1.
- Вставляемое число: 1, стек не пуст, 1 = minEle, вставить 1 в стек и minEle = 1.
- Вставляемое число: -1, стек не пуст, -1 < minEle, вставить (2*-1 – 1 = -3) в стек и minEle = -1.
Поп()
- Изначально минимальный элемент minEle в стеке равен -1.
- Удаленное число: -3, поскольку -3 меньше минимального элемента, исходное удаляемое число равно minEle, что равно -1, а новое minEle = 2*-1 – (-3) = 1
- Удаленное число: 1, 1 == minEle, поэтому удаленное число равно 1, а minEle по-прежнему равно 1.
- Число удалено: 0, 0< minEle, исходное число — minEle, равное 1, и новое minEle = 2*1 — 0 = 2.
- Число удалено: 1, 1< minEle, исходное число — minEle, равное 2, и новое minEle = 2*2 — 1 = 3.
- Число удалено: 5, 5> minEle, исходное число 5, а minEle по-прежнему 3.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(1) для каждой операции
Вспомогательное пространство: O(1)