Создайте динамический стек, используя массивы, которые поддерживают getMin() за время O(1) и дополнительное пространство O(1).

Разработайте специальный динамический стек с использованием массива, который поддерживает все операции стека, такие как push() , pop() , peek() , isEmpty() и getMin() с постоянной сложностью времени и пространства.

Примеры:

Assuming the right to left orientation as the top to bottom orientation and performing the operations:

1. Push(10): 10 is added to the top of the stack. Thereafter, the stack modifies to {10}.
2. Push(4): 4 is added to the top of the stack. Thereafter, the stack modifies to {10, 4}.
3. Push(9): 9 is added to the top of the stack. Thereafter, the stack modifies to {10, 4, 9}.
4. Push(6): 6 is added to the top of the stack. Thereafter, the stack modifies to {10, 4, 9, 6}.
5. Push(5): 5 is added to the top of the stack. Thereafter, the stack modifies to {10, 4, 9, 6, 5}.
6. Peek(): Prints the top element of the stack 5.
7. getMin(): Prints the minimum element of the stack 4.
8. Pop(): Deletes the top most element, 5 from the stack. Thereafter, the stack modifies to {10, 4, 9, 6}.
9. Pop(): Deletes the top most element, 6 from the stack. Thereafter, the stack modifies to {10, 4, 9}.
10. Pop(): Deletes the top most element, 9 from the stack. Thereafter, the stack modifies to {10, 4}.
11. Pop(): Deletes the top most element, 4 from the stack. Thereafter, the stack modifies to {10}.
12. Peek(): Prints the top element of the stack 10.
13. 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 ».

Иллюстрация:

Нажмите (х)

• Число для вставки: 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)