La tarea es diseñar una pila que pueda obtener el valor máximo en la pila en tiempo O(1) sin usar una pila adicional.
Ejemplos:
Entrada:
push(2)
findMax()
push(6)
findMax()
pop()
findMax()
Salida:
2 insertados en la pila
Valor máximo en la pila: 2
6 insertados en la pila
Valor máximo en la pila: 6
Elemento extraído
Valor máximo en la pila: 2
Enfoque: en lugar de empujar un solo elemento a la pila, empuja un par en su lugar. El par consta de (valor, localMax) donde localMax es el valor máximo hasta ese elemento.
- Cuando insertamos un nuevo elemento, si el nuevo elemento es mayor que el máximo local debajo de él, establecemos el máximo local de un nuevo elemento igual al elemento mismo.
- De lo contrario, establecemos el máximo local del nuevo elemento igual al máximo local del elemento debajo de él.
- El máximo local de la parte superior de la pila será el máximo general.
- Ahora, si queremos saber el máximo en cualquier punto dado, le preguntamos a la parte superior de la pila por el máximo local asociado con él, lo que se puede hacer en O(1).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <iostream> using namespace std; struct Block { // A block has two elements // as components int value, localMax; }; class Stack { private: // Pointer of type block, // Will be useful later as the // size can be dynamically allocated struct Block* S; int size, top; public: Stack(int); void push(int); void pop(); void max(); }; Stack::Stack(int n) { // Setting size of stack and // initial value of top size = n; S = new Block[n]; top = -1; } // Function to push an element to the stack void Stack::push(int n) { // Doesn't allow pushing elements // if stack is full if (top == size - 1) { cout << "Stack is full" << endl; } else { top++; // If the inserted element is the first element // then it is the maximum element, since no other // elements is in the stack, so the localMax // of the first element is the element itself if (top == 0) { S[top].value = n; S[top].localMax = n; } else { // If the newly pushed element is // less than the localMax of element below it, // Then the over all maximum doesn't change // and hence, the localMax of the newly inserted // element is same as element below it if (S[top - 1].localMax > n) { S[top].value = n; S[top].localMax = S[top - 1].localMax; } // Newly inserted element is greater than the localMax // below it, hence the localMax of new element // is the element itself else { S[top].value = n; S[top].localMax = n; } } cout << n << " inserted in stack" << endl; } } // Function to remove an element // from the top of the stack void Stack::pop() { // If stack is empty if (top == -1) { cout << "Stack is empty" << endl; } // Remove the element if the stack // is not empty else { top--; cout << "Element popped" << endl; } } // Function to find the maximum // element from the stack void Stack::max() { // If stack is empty if (top == -1) { cout << "Stack is empty" << endl; } else { // The overall maximum is the local maximum // of the top element cout << "Maximum value in the stack: " << S[top].localMax << endl; } } // Driver code int main() { // Create stack of size 5 Stack S1(5); S1.push(2); S1.max(); S1.push(6); S1.max(); S1.pop(); S1.max(); return 0; }
Java
// Java implementation of the approach class GFG { static class Block { // A block has two elements // as components int value, localMax; }; static class Stack { // Pointer of type block, // Will be useful later as the // size can be dynamically allocated Block S[]; int size, top; Stack(int n) { // Setting size of stack and // initial value of top size = n; S = new Block[n]; for(int i=0;i<n;i++)S[i]=new Block(); top = -1; } // Function to push an element to the stack void push(int n) { // Doesn't allow pushing elements // if stack is full if (top == size - 1) { System.out.print( "Stack is full" ); } else { top++; // If the inserted element is the first element // then it is the maximum element, since no other // elements is in the stack, so the localMax // of the first element is the element itself if (top == 0) { S[top].value = n; S[top].localMax = n; } else { // If the newly pushed element is // less than the localMax of element below it, // Then the over all maximum doesn't change // and hence, the localMax of the newly inserted // element is same as element below it if (S[top - 1].localMax > n) { S[top].value = n; S[top].localMax = S[top - 1].localMax; } // Newly inserted element is greater than the localMax // below it, hence the localMax of new element // is the element itself else { S[top].value = n; S[top].localMax = n; } } System.out.println( n + " inserted in stack" ); } } // Function to remove an element // from the top of the stack void pop() { // If stack is empty if (top == -1) { System.out.println( "Stack is empty"); } // Remove the element if the stack // is not empty else { top--; System.out.println( "Element popped" ); } } // Function to find the maximum // element from the stack void max() { // If stack is empty if (top == -1) { System.out.println( "Stack is empty"); } else { // The overall maximum is the local maximum // of the top element System.out.println( "Maximum value in the stack: "+ S[top].localMax); } } } // Driver code public static void main(String args[]) { // Create stack of size 5 Stack S1=new Stack(5); S1.push(2); S1.max(); S1.push(6); S1.max(); S1.pop(); S1.max(); } } // This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach class Block: # A block has two elements # as components (i.e. value and localMax) def __init__(self, value, localMax): self.value = value self.localMax = localMax class Stack: def __init__(self, size): # Setting size of stack and # initial value of top self.stack = [None] * size self.size = size self.top = -1 # Function to push an element # to the stack def push(self, value): # Don't allow pushing elements # if stack is full if self.top == self.size - 1: print("Stack is full") else: self.top += 1 # If the inserted element is the first element # then it is the maximum element, since no other # elements is in the stack, so the localMax # of the first element is the element itself if self.top == 0: self.stack[self.top] = Block(value, value) else: # If the newly pushed element is less # than the localMax of element below it, # Then the over all maximum doesn't change # and hence, the localMax of the newly inserted # element is same as element below it if self.stack[self.top - 1].localMax > value: self.stack[self.top] = Block( value, self.stack[self.top - 1].localMax) # Newly inserted element is greater than # the localMax below it, hence the localMax # of new element is the element itself else: self.stack self.stack[self.top] = Block(value, value) print(value, "inserted in the stack") # Function to remove an element # from the top of the stack def pop(self): # If stack is empty if self.top == -1: print("Stack is empty") # Remove the element if the stack # is not empty else: self.top -= 1 print("Element popped") # Function to find the maximum # element from the stack def max(self): # If stack is empty if self.top == -1: print("Stack is empty") else: # The overall maximum is the local maximum # of the top element print("Maximum value in the stack:", self.stack[self.top].localMax) # Driver code # Create stack of size 5 stack = Stack(5) stack.push(2) stack.max() stack.push(6) stack.max() stack.pop() stack.max() # This code is contributed by girishthatte
C#
// C# implementation of the approach using System; class GFG { public class Block { // A block has two elements // as components public int value, localMax; }; public class Stack { // Pointer of type block, // Will be useful later as the // size can be dynamically allocated public Block []S; public int size, top; public Stack(int n) { // Setting size of stack and // initial value of top size = n; S = new Block[n]; for(int i = 0; i < n; i++)S[i] = new Block(); top = -1; } // Function to push an element to the stack public void push(int n) { // Doesn't allow pushing elements // if stack is full if (top == size - 1) { Console.Write( "Stack is full" ); } else { top++; // If the inserted element is the first element // then it is the maximum element, since no other // elements is in the stack, so the localMax // of the first element is the element itself if (top == 0) { S[top].value = n; S[top].localMax = n; } else { // If the newly pushed element is // less than the localMax of element below it, // Then the over all maximum doesn't change // and hence, the localMax of the newly inserted // element is same as element below it if (S[top - 1].localMax > n) { S[top].value = n; S[top].localMax = S[top - 1].localMax; } // Newly inserted element is greater than the localMax // below it, hence the localMax of new element // is the element itself else { S[top].value = n; S[top].localMax = n; } } Console.WriteLine( n + " inserted in stack" ); } } // Function to remove an element // from the top of the stack public void pop() { // If stack is empty if (top == -1) { Console.WriteLine( "Stack is empty"); } // Remove the element if the stack // is not empty else { top--; Console.WriteLine( "Element popped" ); } } // Function to find the maximum // element from the stack public void max() { // If stack is empty if (top == -1) { Console.WriteLine( "Stack is empty"); } else { // The overall maximum is the local maximum // of the top element Console.WriteLine( "Maximum value in the stack: "+ S[top].localMax); } } } // Driver code public static void Main(String []args) { // Create stack of size 5 Stack S1 = new Stack(5); S1.push(2); S1.max(); S1.push(6); S1.max(); S1.pop(); S1.max(); } } // This code contributed by Rajput-Ji
Javascript
<script> /// JavaScript implementation of the approach class Block{ /// A block has two elements /// as components (i.e. value and localMax) constructor(value, localMax){ this.value = value this.localMax = localMax } } class Stack{ constructor(size){ /// Setting size of stack and /// initial value of top this.stack = new Array(size).fill(null) this.size = size this.top = -1 } // Function to push an element // to the stack push(value){ // Don't allow pushing elements // if stack is full if(this.top == this.size - 1) document.write("Stack is full","</br>") else{ this.top += 1 // If the inserted element is the first element // then it is the maximum element, since no other // elements is in the stack, so the localMax // of the first element is the element itthis if(this.top == 0) this.stack[this.top] = new Block(value, value) else{ // If the newly pushed element is less // than the localMax of element below it, // Then the over all maximum doesn't change // and hence, the localMax of the newly inserted // element is same as element below it if(this.stack[this.top - 1].localMax > value){ this.stack[this.top] = new Block( value, this.stack[this.top - 1].localMax) } // Newly inserted element is greater than // the localMax below it, hence the localMax // of new element is the element itthis else{ this.stack[this.top] = new Block(value, value) } } document.write(value, "inserted in the stack","</br>") } } // Function to remove an element // from the top of the stack pop(){ // If stack is empty if(this.top == -1) document.write("Stack is empty","</br>") // Remove the element if the stack // is not empty else{ this.top -= 1 document.write("Element popped","</br>") } } // Function to find the maximum // element from the stack max(){ // If stack is empty if(this.top == -1) document.write("Stack is empty","</br>") else{ // The overall maximum is the local maximum // of the top element document.write("Maximum value in the stack:",this.stack[this.top].localMax,"</br>") } } } // Driver code // Create stack of size 5 let stack = new Stack(5) stack.push(2) stack.max() stack.push(6) stack.max() stack.pop() stack.max() /// This code is contributed by shinjanpatra </script>
2 inserted in stack Maximum value in the stack: 2 6 inserted in stack Maximum value in the stack: 6 Element popped Maximum value in the stack: 2
Complejidad de tiempo : O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por RuchaDeodhar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA