Dada una pila de enteros. La tarea es diseñar una pila especial de modo que el elemento máximo se pueda encontrar en O(1) tiempo y O(1) espacio extra.
Ejemplos :
Given Stack : 2 5 1 64 --> Maximum So Output must be 64 when getMax() is called.
A continuación se muestran las diferentes funciones diseñadas para empujar y sacar elementos de la pila.
Push(x) : Inserta x en la parte superior de la pila.
- Si la pila está vacía, inserte x en la pila y haga que maxEle sea igual a x.
- Si la pila no está vacía, compare x con maxEle. Se presentan dos casos:
- Si x es menor o igual que maxEle, simplemente inserte x.
- Si x es mayor que maxEle, inserte (2*x – maxEle) en la pila y haga que maxEle sea igual a x. Por ejemplo, el maxEle anterior era 3. Ahora queremos insertar 4. Actualizamos maxEle como 4 e insertamos 2*4 – 3 = 5 en la pila.
Pop(): elimina un elemento de la parte superior de la pila.
- Retire el elemento de la parte superior. Sea y el elemento eliminado. Se presentan dos casos:
- Si y es menor o igual que maxEle, el elemento máximo en la pila sigue siendo maxEle.
- Si y es mayor que maxEle, el elemento máximo ahora se convierte en (2*maxEle – y), así que actualice (maxEle = 2*maxEle – y). Aquí es donde recuperamos el máximo anterior del máximo actual y su valor en la pila. Por ejemplo, deje que el elemento a eliminar sea 5 y maxEle sea 4. Eliminamos 5 y actualizamos maxEle como 2*4 – 5 = 3.
Puntos importantes:
- La pila no contiene el valor real de un elemento si es máximo hasta ahora.
- El elemento máximo real siempre se almacena en maxEle
Ilustración
empujar (x)
- Número a insertar: 3, la pila está vacía, así que inserte 3 en la pila y maxEle = 3.
- Número a insertar: 5, la pila no está vacía, 5> maxEle, inserte (2*5-3) en la pila y maxEle = 5.
- Número a insertar: 2, la pila no está vacía, 2< maxEle, inserte 2 en la pila y maxEle = 5.
- Número a insertar: 1, la pila no está vacía, 1< maxEle, inserte 1 en la pila y maxEle = 5.
Estallido()
- Inicialmente, el elemento máximo maxEle en la pila es 5.
- Número eliminado: 1, dado que 1 es menor que maxEle, simplemente extraiga 1. maxEle = 5.
- Número eliminado: 2, 2<maxEle, por lo que el número eliminado es 2 y maxEle sigue siendo igual a 5.
- Número eliminado: 7, 7> maxEle, el número original es maxEle, que es 5 y el nuevo maxEle = 2*5 – 7 = 3.
C++
// C++ program to implement a stack that supports
// getMaximum() in O(1) time and O(1) extra space.
#include <bits/stdc++.h>
using namespace std;
// A user defined stack that supports getMax() in
// addition to push() and pop()
struct MyStack {
stack<int> s;
int maxEle;
// Prints maximum element of MyStack
void getMax()
{
if (s.empty())
cout << "Stack is empty\n";
// variable maxEle stores the maximum element
// in the stack.
else
cout << "Maximum Element in the stack is: "
<< maxEle << "\n";
}
// Prints top element of MyStack
void peek()
{
if (s.empty()) {
cout << "Stack is empty ";
return;
}
int t = s.top(); // Top element.
cout << "Top Most Element is: ";
// If t < maxEle means maxEle stores
// value of t.
(t > maxEle) ? cout << maxEle : cout << t;
}
// Remove the top element from MyStack
void pop()
{
if (s.empty()) {
cout << "Stack is empty\n";
return;
}
cout << "Top Most Element Removed: ";
int t = s.top();
s.pop();
// Maximum will change as the maximum element
// of the stack is being removed.
if (t > maxEle) {
cout << maxEle << "\n";
maxEle = 2 * maxEle - t;
}
else
cout << t << "\n";
}
// Removes top element from MyStack
void push(int x)
{
// Insert new number into the stack
if (s.empty()) {
maxEle = x;
s.push(x);
cout << "Number Inserted: " << x << "\n";
return;
}
// If new number is greater than maxEle
if (x > maxEle) {
s.push(2 * x - maxEle);
maxEle = x;
}
else
s.push(x);
cout << "Number Inserted: " << x << "\n";
}
};
// Driver Code
int main()
{
MyStack s;
s.push(3);
s.push(5);
s.getMax();
s.push(7);
s.push(19);
s.getMax();
s.pop();
s.getMax();
s.pop();
s.peek();
return 0;
}
Java
// Java program to implement a stack that supports
// getMaximum() in O(1) time and O(1) extra space.
import java.util.*;
class GFG
{
// A user defined stack that supports getMax() in
// addition to push() and pop()
static class MyStack
{
Stack<Integer> s = new Stack<Integer>();
int maxEle;
// Prints maximum element of MyStack
void getMax()
{
if (s.empty())
System.out.print("Stack is empty\n");
// variable maxEle stores the maximum element
// in the stack.
else
System.out.print("Maximum Element in" +
"the stack is: "+maxEle + "\n");
}
// Prints top element of MyStack
void peek()
{
if (s.empty())
{
System.out.print("Stack is empty ");
return;
}
int t = s.peek(); // Top element.
System.out.print("Top Most Element is: ");
// If t < maxEle means maxEle stores
// value of t.
if(t > maxEle)
System.out.print(maxEle);
else
System.out.print(t);
}
// Remove the top element from MyStack
void pop()
{
if (s.empty())
{
System.out.print("Stack is empty\n");
return;
}
System.out.print("Top Most Element Removed: ");
int t = s.peek();
s.pop();
// Maximum will change as the maximum element
// of the stack is being removed.
if (t > maxEle)
{
System.out.print(maxEle + "\n");
maxEle = 2 * maxEle - t;
}
else
System.out.print(t + "\n");
}
// Removes top element from MyStack
void push(int x)
{
// Insert new number into the stack
if (s.empty())
{
maxEle = x;
s.push(x);
System.out.print("Number Inserted: " + x + "\n");
return;
}
// If new number is less than maxEle
if (x > maxEle)
{
s.push(2 * x - maxEle);
maxEle = x;
}
else
s.push(x);
System.out.print("Number Inserted: " + x + "\n");
}
};
// Driver Code
public static void main(String[] args)
{
MyStack s = new MyStack();
s.push(3);
s.push(5);
s.getMax();
s.push(7);
s.push(19);
s.getMax();
s.pop();
s.getMax();
s.pop();
s.peek();
}
}
/* This code contributed by PrinciRaj1992 */
Python 3
# 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.maximum = None
#This method returns the string representation of the object (stack).
def __str__(self):
temp=self.top
out=[]
while temp:
out.append(str(temp.value))
temp=temp.next
out='\n'.join(out)
return ('Top {} \n\nStack :\n{}'.format(self.top,out))
# __repr__ is same as __str__
__repr__=__str__
#This method is used to get minimum element of stack
def getMax(self):
if self.top is None:
return "Stack is empty"
else:
print("Maximum Element in the stack is: {}" .format(self.maximum))
# 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.maximum:
print("Top Most Element is: {}" .format(self.maximum))
else:
print("Top Most Element is: {}" .format(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.maximum = value
elif value > self.maximum :
temp = (2 * value) - self.maximum
new_node = Node(temp)
new_node.next = self.top
self.top = new_node
self.maximum = value
else:
new_node = Node(value)
new_node.next = self.top
self.top = new_node
print("Number Inserted: {}" .format(value))
#This method is used to pop top of stack
def pop(self):
if self.top is None:
print( "Stack is empty")
else:
removedNode = self.top.value
self.top = self.top.next
if removedNode > self.maximum:
print ("Top Most Element Removed :{} " .format(self.maximum))
self.maximum = ( ( 2 * self.maximum ) - removedNode )
else:
print ("Top Most Element Removed : {}" .format(removedNode))
# Driver program to test above class
stack = Stack()
stack.push(3)
stack.push(5)
stack.getMax()
stack.push(7)
stack.push(19)
stack.getMax()
stack.pop()
stack.getMax()
stack.pop()
stack.peek()
# This code is contributed by Blinkii
C#
// C# program to implement a stack that supports
// getMaximum() in O(1) time and O(1) extra space.
using System;
using System.Collections.Generic;
class GFG
{
// A user defined stack that supports getMax() in
// addition to push() and pop()
public class MyStack
{
public Stack<int> s = new Stack<int>();
public int maxEle;
// Prints maximum element of MyStack
public void getMax()
{
if (s.Count == 0)
Console.Write("Stack is empty\n");
// variable maxEle stores the maximum element
// in the stack.
else
Console.Write("Maximum Element in" +
"the stack is: "+maxEle + "\n");
}
// Prints top element of MyStack
public void peek()
{
if (s.Count == 0)
{
Console.Write("Stack is empty ");
return;
}
int t = s.Peek(); // Top element.
Console.Write("Top Most Element is: ");
// If t < maxEle means maxEle stores
// value of t.
if(t > maxEle)
Console.Write(maxEle);
else
Console.Write(t);
}
// Remove the top element from MyStack
public void pop()
{
if (s.Count == 0)
{
Console.Write("Stack is empty\n");
return;
}
Console.Write("Top Most Element Removed: ");
int t = s.Peek();
s.Pop();
// Maximum will change as the maximum element
// of the stack is being removed.
if (t > maxEle)
{
Console.Write(maxEle + "\n");
maxEle = 2 * maxEle - t;
}
else
Console.Write(t + "\n");
}
// Removes top element from MyStack
public void push(int x)
{
// Insert new number into the stack
if (s.Count == 0)
{
maxEle = x;
s.Push(x);
Console.Write("Number Inserted: " + x + "\n");
return;
}
// If new number is less than maxEle
if (x > maxEle)
{
s.Push(2 * x - maxEle);
maxEle = x;
}
else
s.Push(x);
Console.Write("Number Inserted: " + x + "\n");
}
};
// Driver Code
public static void Main(String[] args)
{
MyStack s = new MyStack();
s.push(3);
s.push(5);
s.getMax();
s.push(7);
s.push(19);
s.getMax();
s.pop();
s.getMax();
s.pop();
s.peek();
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to implement a stack that supports
// getMaximum() in O(1) time and O(1) extra space.
let s = [];
let maxEle;
// Prints maximum element of MyStack
function getMax()
{
if (s.length == 0)
document.write("Stack is empty" + "</br>");
// variable maxEle stores the maximum element
// in the stack.
else
document.write("Maximum Element in " +
"the stack is: "+maxEle + "</br>");
}
// Prints top element of MyStack
function peek()
{
if (s.length == 0)
{
document.write("Stack is empty ");
return;
}
let t = s[s.length - 1]; // Top element.
document.write("Top Most Element is: ");
// If t < maxEle means maxEle stores
// value of t.
if(t > maxEle)
document.write(maxEle);
else
document.write(t);
}
// Remove the top element from MyStack
function pop()
{
if (s.length == 0)
{
document.write("Stack is empty" + "</br>");
return;
}
document.write("Top Most Element Removed: ");
let t = s[s.length - 1];
s.pop();
// Maximum will change as the maximum element
// of the stack is being removed.
if (t > maxEle)
{
document.write(maxEle + "</br>");
maxEle = 2 * maxEle - t;
}
else
document.write(t + "</br>");
}
// Removes top element from MyStack
function push(x)
{
// Insert new number into the stack
if (s.length == 0)
{
maxEle = x;
s.push(x);
document.write("Number Inserted: " + x + "</br>");
return;
}
// If new number is less than maxEle
if (x > maxEle)
{
s.push(2 * x - maxEle);
maxEle = x;
}
else
s.push(x);
document.write("Number Inserted: " + x + "</br>");
}
push(3);
push(5);
getMax();
push(7);
push(19);
getMax();
pop();
getMax();
pop();
peek();
// This code is contributed by rameshtravel07.
</script>
Producción:
Number Inserted: 3 Number Inserted: 5 Maximum Element in the stack is: 5 Number Inserted: 7 Number Inserted: 19 Maximum Element in the stack is: 19 Top Most Element Removed: 19 Maximum Element in the stack is: 7 Top Most Element Removed: 7 Top Most Element is: 5
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)