Создайте стек для получения исходных элементов и возврата минимального элемента за время O (1) и пространство O (1)
Наша задача - разработать структуру данных SpecialStack, которая поддерживает все операции со стеком, такие как push () , pop () , isEmpty () , isFull () и дополнительную операцию getMin ( ), которая должна возвращать минимальный элемент из SpecialStack. Все эти операции SpecialStack должны выполняться с временной сложностью O (1). Чтобы реализовать SpecialStack, вы должны использовать только стандартную структуру данных Stack и никаких других структур данных, таких как массивы, список и т. Д.
Пример:
Рассмотрим следующий специальный стек 16 -> ТОП 15 29 19 18 Когда вызывается getMin (), он должен вернуть 15, что является минимумом. элемент в текущем стеке. Если мы дважды вытолкнем стек, стек станет 29 -> ТОП 19 18 Когда вызывается getMin (), он должен вернуть 18, что является минимумом. в текущем стеке.
Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.
Здесь обсуждается подход, который использует O (1) время и O (1) дополнительное пространство. Однако в предыдущей статье исходные элементы не восстанавливаются. В любой момент времени возвращается только минимальный элемент.
В этой статье предыдущий подход изменен таким образом, что исходные элементы также могут быть извлечены во время операции pop ().
Подход:
Рассмотрим переменный минимум, в котором мы храним минимальный элемент в стеке. А что, если мы вытолкнем минимальный элемент из стека? Как обновить минимальную переменную до следующего минимального значения? Одно из решений - поддерживать другой стек в отсортированном порядке, чтобы наименьший элемент всегда был наверху. Однако это пространственный подход O (n).
Чтобы достичь этого в пространстве O (1) , нам нужен способ сохранить текущее значение элемента и следующее минимальное значение в одном и том же узле. Это можно сделать, применив простую математику:
new_value = 2*current_value - minimum
Мы помещаем это new_value в стек вместо current_value. Чтобы получить current_value и следующий минимум из new_value:
текущее_значение = (новое_значение + минимум) / 2 минимум = новое_значение - 2 * текущее
Когда операция Push (x) выполнена, мы следуем приведенному ниже алгоритму:
- If stack is empty
- insert x into the stack
- make minimum equal to x.
- If stack is not empty
- if x is less than minimum
- set temp equal to 2*x-minimum
- set minimum equal to x
- set x equal to temp
- insert x into stack
Когда операция Pop (x) выполнена, мы следуем приведенному ниже алгоритму:
- If stack is not empty
- set x equal to topmost element
- if x is less than minimum
- set minimum equal to 2*minimum – x
- set x equal to (x+minimum)/2
- return x
When getMin() is called, we return the element stored in variable, minimum:
Java
// Java program to retrieve original elements of the // from a Stack which returns the minimum element // in O(1) time and O(1) space class Stack { Node top; // Stores minimum element of the stack int minimum; // Function to push an element void push(Node node) { int current = node.getData(); if (top == null ) { top = node; minimum = current; } else { if (current < minimum) { node.setData( 2 * current - minimum); minimum = current; } node.setNext(top); top = node; } } // Retrieves topmost element Node pop() { Node node = top; if (node != null ) { int current = node.getData(); if (current < minimum) { minimum = 2 * minimum - current; node.setData((current + minimum) / 2 ); } top = top.getNext(); } return node; } // Retrieves topmost element without // popping it from the stack Node peek() { Node node = null ; if (top != null ) { node = new Node(); int current = top.getData(); node.setData(current < minimum ? minimum : current); } return node; } // Function to print all elements in the stack void printAll() { Node ptr = top; int min = minimum; if (ptr != null ) { // if stack is not empty while ( true ) { int val = ptr.getData(); if (val < min) { min = 2 * min - val; val = (val + min) / 2 ; } System.out.print(val + " " ); ptr = ptr.getNext(); if (ptr == null ) break ; } System.out.println(); } else System.out.println( "Empty!" ); } // Returns minimum of Stack int getMin() { return minimum; } boolean isEmpty() { return top == null ; } } // Node class which contains data // and pointer to next node class Node { int data; Node next; Node() { data = - 1 ; next = null ; } Node( int d) { data = d; next = null ; } void setData( int data) { this .data = data; } void setNext(Node next) { this .next = next; } Node getNext() { return next; } int getData() { return data; } } // Driver Code public class Main { public static void main(String[] args) { // Create a new stack Stack stack = new Stack(); Node node; // Push the element into the stack stack.push( new Node( 5 )); stack.push( new Node( 3 )); stack.push( new Node( 4 )); // Calls the method to print the stack System.out.println( "Elements in the stack are:" ); stack.printAll(); // Print current minimum element if stack is // not empty System.out.println(stack.isEmpty() ? "
Empty Stack!" : "
Minimum: " + stack.getMin()); // Push new elements into the stack stack.push( new Node( 1 )); stack.push( new Node( 2 )); // Printing the stack System.out.println( "
Stack after adding new elements:" ); stack.printAll(); // Print current minimum element if stack is // not empty System.out.println(stack.isEmpty() ? "
Empty Stack!" : "
Minimum: " + stack.getMin()); // Pop elements from the stack node = stack.pop(); System.out.println( "
Element Popped: " + (node == null ? "Empty!" : node.getData())); node = stack.pop(); System.out.println( "Element Popped: " + (node == null ? "Empty!" : node.getData())); // Printing stack after popping elements System.out.println( "
Stack after removing top two elements:" ); stack.printAll(); // Printing current Minimum element in the stack System.out.println(stack.isEmpty() ? "
Empty Stack!" : "
Minimum: " + stack.getMin()); // Printing top element of the stack node = stack.peek(); System.out.println( "
Top: " + (node == null ? "
Empty!" : node.getData())); } } |
Python3
""" Python program to retrieve original elements of the from a Stack which returns the minimum element in O(1) time and O(1) space """ # Class to make a Node class Node: # Constructor which assign argument to nade"s value def __init__( self , value): self .value = value self . next = None # This method returns the string # representation of the object. def __str__( self ): return "Node({})" . format ( self .value) # __repr__ is same as __str__ __repr__ = __str__ class Stack: # Stack Constructor initialise # top of stack and counter. def __init__( self ): self .top = None self .count = 0 self .minimum = None # This method returns the string # representation of the object (stack). def __str__( self ): temp = self .top m = self .minimum out = [] if temp is None : print ( "Empty Stack" ) else : while not temp is None : val = temp.value if val < m: m = ( 2 * m) - val val = ( val + m ) / 2 out.append( str ( int (val))) temp = temp. next out = " " .join(out) return (out) # __repr__ is same as __str__ __repr__ = __str__ # This method is used to get minimum element of stack def getMin( self ): if self .top is None : return "Stack is empty" else : return self .minimum # Method to check if Stack is Empty or not def isEmpty( self ): # If top equals to None then stack is empty if self .top = = None : return True else : # If top not equal to None then stack is empty return False # This method returns length of stack def __len__( self ): self .count = 0 tempNode = self .top while tempNode: tempNode = tempNode. next self .count + = 1 return self .count # This method returns top of stack def peek( self ): if self .top is None : print ( "Stack is empty" ) else : if self .top.value < self .minimum: return self .minimum else : return self .top.value # This method is used to add node to stack def push( self ,value): if self .top is None : self .top = Node(value) self .minimum = value else : new_node = Node(value) if value < self .minimum: temp = ( 2 * value) - self .minimum new_node.value = temp self .minimum = value new_node. next = self .top self .top = new_node # This method is used to pop top of stack def pop( self ): new_node = self .top if self .top is None : print ( "Stack is empty" ) else : removedNode = new_node.value if removedNode < self .minimum: self .minimum = ( ( 2 * self
РЕКОМЕНДУЕМЫЕ СТАТЬИ |