Improve Article
Save Article
Like Article
Improve Article
Save Article
Like Article
Given a stack of integers. The task is to design a special stack such that the maximum element can be found in O(1) time and O(1) extra space.
Examples:
Given Stack : 2 5 1 64 --> Maximum So Output must be 64 when getMax() is called.
Below are the different functions designed to push and pop elements from the stack.
Push(x) : Inserts x at the top of stack.
- If stack is empty, insert x into the stack and make maxEle equal to x.
- If stack is not empty, compare x with maxEle. Two cases arise:
- If x is less than or equal to maxEle, simply insert x.
- If x is greater than maxEle, insert (2*x – maxEle) into the stack and make maxEle equal to x. For example, let previous maxEle was 3. Now we want to insert 4. We update maxEle as 4 and insert 2*4 – 3 = 5 into the stack.
Pop() : Removes an element from top of stack.
- Remove element from top. Let the removed element be y. Two cases arise:
- If y is less than or equal to maxEle, the maximum element in the stack is still maxEle.
- If y is greater than maxEle, the maximum element now becomes (2*maxEle – y), so update (maxEle = 2*maxEle – y). This is where we retrieve previous maximum from current maximum and its value in stack. For example, let the element to be removed be 5 and maxEle be 4. We remove 5 and update maxEle as 2*4 – 5 = 3.]
How does the Above Equation work?
While pushing x into stack if x is greater than maxEle we push modified value = 2 * x-maxEle.
So, x > val
=> x-val>0
=> adding x to both sides 2x – val >x (this is our updated maxEle from next steps).
Means the modified value is greater than maxEle.
After popped out the maxEle should be updated
so maxEle = 2*maxEle – y (top value)
= 2*maxEle – (2*x- previousMax)
= 2*maxEle – 2*maxEle (maxELe = x in next steps) + previousMax
= previousMax.
Important Points:
- Stack doesn’t hold actual value of an element if it is maximum so far.
- Actual maximum element is always stored in maxEle
Illustration:
Push(x):
- Number to be Inserted: 3, Stack is empty, so insert 3 into stack, and maxEle = 3.
- Number to be Inserted: 5, Stack is not empty, 5> maxEle, insert (2*5-3) into stack and maxEle = 5.
- Number to be Inserted: 2, Stack is not empty, 2< maxEle, insert 2 into stack and maxEle = 5.
- Number to be Inserted: 1, Stack is not empty, 1< maxEle, insert 1 into stack and maxEle = 5.
Pop() :
- Initially the maximum element maxEle in the stack is 5.
- Number removed: 1, Since 1 is less than maxEle just pop 1. maxEle=5.
- Number removed: 2, 2<maxEle, so number removed is 2 and maxEle is still equal to 5.
- Number removed: 7, 7> maxEle, original number is maxEle which is 5 and new maxEle = 2*5 – 7 = 3.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
struct MyStack {
stack<int> s;
int maxEle;
void getMax()
{
if (s.empty())
cout << "Stack is emptyn";
else
cout << "Maximum Element in the stack is: "
<< maxEle << "n";
}
void peek()
{
if (s.empty()) {
cout << "Stack is empty ";
return;
}
int t = s.top();
cout << "Top Most Element is: ";
(t > maxEle) ? cout << maxEle : cout << t;
}
void pop()
{
if (s.empty()) {
cout << "Stack is emptyn";
return;
}
cout << "Top Most Element Removed: ";
int t = s.top();
s.pop();
if (t > maxEle) {
cout << maxEle << "n";
maxEle = 2 * maxEle - t;
}
else
cout << t << "n";
}
void push(int x)
{
if (s.empty()) {
maxEle = x;
s.push(x);
cout << "Number Inserted: " << x << "n";
return;
}
if (x > maxEle) {
s.push(2 * x - maxEle);
maxEle = x;
}
else
s.push(x);
cout << "Number Inserted: " << x << "n";
}
};
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
import java.util.*;
class GFG
{
static class MyStack
{
Stack<Integer> s = new Stack<Integer>();
int maxEle;
void getMax()
{
if (s.empty())
System.out.print("Stack is emptyn");
else
System.out.print("Maximum Element in" +
"the stack is: "+maxEle + "n");
}
void peek()
{
if (s.empty())
{
System.out.print("Stack is empty ");
return;
}
int t = s.peek();
System.out.print("Top Most Element is: ");
if(t > maxEle)
System.out.print(maxEle);
else
System.out.print(t);
}
void pop()
{
if (s.empty())
{
System.out.print("Stack is emptyn");
return;
}
System.out.print("Top Most Element Removed: ");
int t = s.peek();
s.pop();
if (t > maxEle)
{
System.out.print(maxEle + "n");
maxEle = 2 * maxEle - t;
}
else
System.out.print(t + "n");
}
void push(int x)
{
if (s.empty())
{
maxEle = x;
s.push(x);
System.out.print("Number Inserted: " + x + "n");
return;
}
if (x > maxEle)
{
s.push(2 * x - maxEle);
maxEle = x;
}
else
s.push(x);
System.out.print("Number Inserted: " + x + "n");
}
};
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();
}
}
Python 3
class Node:
def __init__(self, value):
self.value = value
self.next = None
def __str__(self):
return "Node({})".format(self.value)
__repr__ = __str__
class Stack:
def __init__(self):
self.top = None
self.count = 0
self.maximum = None
def __str__(self):
temp=self.top
out=[]
while temp:
out.append(str(temp.value))
temp=temp.next
out='n'.join(out)
return ('Top {} nnStack :n{}'.format(self.top,out))
__repr__=__str__
def getMax(self):
if self.top is None:
return "Stack is empty"
else:
print("Maximum Element in the stack is: {}" .format(self.maximum))
def isEmpty(self):
if self.top == None:
return True
else:
return False
def __len__(self):
self.count = 0
tempNode = self.top
while tempNode:
tempNode = tempNode.next
self.count+=1
return self.count
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))
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))
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))
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()
C#
using System;
using System.Collections.Generic;
class GFG
{
public class MyStack
{
public Stack<int> s = new Stack<int>();
public int maxEle;
public void getMax()
{
if (s.Count == 0)
Console.Write("Stack is emptyn");
else
Console.Write("Maximum Element in" +
"the stack is: "+maxEle + "n");
}
public void peek()
{
if (s.Count == 0)
{
Console.Write("Stack is empty ");
return;
}
int t = s.Peek();
Console.Write("Top Most Element is: ");
if(t > maxEle)
Console.Write(maxEle);
else
Console.Write(t);
}
public void pop()
{
if (s.Count == 0)
{
Console.Write("Stack is emptyn");
return;
}
Console.Write("Top Most Element Removed: ");
int t = s.Peek();
s.Pop();
if (t > maxEle)
{
Console.Write(maxEle + "n");
maxEle = 2 * maxEle - t;
}
else
Console.Write(t + "n");
}
public void push(int x)
{
if (s.Count == 0)
{
maxEle = x;
s.Push(x);
Console.Write("Number Inserted: " + x + "n");
return;
}
if (x > maxEle)
{
s.Push(2 * x - maxEle);
maxEle = x;
}
else
s.Push(x);
Console.Write("Number Inserted: " + x + "n");
}
};
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();
}
}
Javascript
<script>
let s = [];
let maxEle;
function getMax()
{
if (s.length == 0)
document.write("Stack is empty" + "</br>");
else
document.write("Maximum Element in " +
"the stack is: "+maxEle + "</br>");
}
function peek()
{
if (s.length == 0)
{
document.write("Stack is empty ");
return;
}
let t = s[s.length - 1];
document.write("Top Most Element is: ");
if(t > maxEle)
document.write(maxEle);
else
document.write(t);
}
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();
if (t > maxEle)
{
document.write(maxEle + "</br>");
maxEle = 2 * maxEle - t;
}
else
document.write(t + "</br>");
}
function push(x)
{
if (s.length == 0)
{
maxEle = x;
s.push(x);
document.write("Number Inserted: " + x + "</br>");
return;
}
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();
</script>
Output
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
Complexity Analysis:
- Time Complexity: O(1)
- Auxiliary Space: O(1)
Last Updated :
03 Nov, 2022
Like Article
Save Article
Hello Everyone!
In this tutorial, we will learn about the working of a Stack and Finding it’s Maximum element in the C++ programming language.
To understand the basic functionality of the Stack, we will recommend you to visit the Stack Data Structure, where we have explained this concept in detail from scratch.
For a better understanding of its implementation, refer to the well-commented C++ code given below.
Code:
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//Function to print the Maximum element in the stack
void findMax(stack<int> s)
{
int m = s.top(); //initialization
int a;
while (!s.empty())
{
a = s.top();
if (m < a)
m = a; //Storing the maximum element in m
s.pop(); //removing the topmost element to bring next element at the top
}
cout << "nnThe maximum element of the Stack is: " << m << endl;
}
//Function to print the elements of the stack
void show(stack<int> s)
{
while (!s.empty())
{
cout << " " << s.top(); //printing the topmost element
s.pop(); //removing the topmost element to bring next element at the top
}
cout << endl;
}
int main()
{
cout << "nnWelcome to Studytonight :-)nnn";
cout << " ===== Program to Find the Maximum element in the Stack, in CPP ===== nn";
int i;
//Stack declaration (stack of integers)
stack<int> s;
//Filling the elements by using the push() method.
cout << "Filling the Stack in LIFO order using the push() method:"; //LIFO= Last In First Out
s.push(4);
s.push(2);
s.push(20);
s.push(12);
s.push(52);
s.push(14);
cout << "nnThe elements of the Stack in LIFO order are: ";
show(s);
findMax(s); //to find the max element
cout << "nnn";
return 0;
}
Output:
We hope that this post helped you develop a better understanding of the concept of Stack and its implementation in C++. For any query, feel free to reach out to us via the comments section down below.
Keep Learning : )
Edit:
without iterating over the Stack
does not actually prohibit all iteration. Rather, the question only prohibits doing the simple
for (Integer i : lifo)
Thus, this solution satisfies the question’s limitations.
Just empty a copy of the stack. pop each of the elements from the copy, checking for max against an integer all the while.
Stack<Integer> lifoCopy = (Stack<Integer>) lifo.clone();
int max = Integer.MIN_VALUE;
while (!lifoCopy.isEmpty())
{
max = Math.max(lifoCopy.pop(), max);
}
System.out.println("max=" + max.toString());
This will work for you in O(n) time even if your interviewers decide to be more restrictive and not allow more built in functions (max, min, sort, etc.).
Additionally, if you need to have the original unharmed, but can’t use clone, you can do so with an extra stack:
Stack<Integer> reverseLifo = new Stack<Integer>();
int max = Integer.MIN_VALUE;
while (!lifo.isEmpty())
{
int val = lifo.pop();
max = Math.max(val, max);
reverseLifo.push(val);
}
while (!reverseLifo.isEmpty())
{
lifo.push(reverseLifo.pop());
}
System.out.println("max=" + max.toString());
Finally, this assumes that comparison against a temp variable is acceptable. If no comparison is allowed at all, then this solution in conjunction with this method will work.
Алгоритмы прекрасны тем, что они могут решать сложные проблемы удивительно простыми способами. Однако полезность алгоритма проявляется и тогда, когда он предлагает более эффективный (или интересный) способ решения достаточно простой задачи.
Предположим, мы хотим найти наибольшее число в стеке, полностью состоящем из целых чисел. Как бы мы это сделали?
Мы должны помнить, что максимальное значение в стеке потенциально может меняться каждый раз, когда мы выталкиваем и выталкиваем из стека. Это особенно заметно в отсортированном стеке с различными значениями, где максимальное значение всегдаизменяется.
Мы не хотим переопределять максимум каждый раз, когда мы помещаем и выталкиваем в стек, если мы можем помочь. И если мы это сделаем, мы не хотим, чтобы процесс поиска был дорогостоящим.
Наивное решение
Ваш первый инстинкт поиска максимального значения в стеке, вероятно, отражен в приведенном ниже коде Ruby, который создает простой класс Stack с добавленным методом «max».
class Stack
def initialize
@stack = []
@max = nil
end
def push(val)
@stack.push(val)
@max = max
end
def pop
@stack.pop
@max = max
end
def peek(index)
raise ArgumentError unless ([email protected]).include?(index)
@stack[index]
end
def max
return nil if @stack.empty?
max = peek(0)
@stack.length.times do |i|
max = @stack[i] if max < @stack[i]
end
max
end
end
Поиск максимума таким образом работает, но не слишком эффективно. Временная сложность метода «max» — это линейное время, или O(n), поскольку нам приходится просматривать весьстек каждый раз, когда мы хотим найти максимальное значение. Мы также запускаем этот алгоритм O(n) каждый раз, когда мы нажимаем и выталкиваем! Там должен быть лучший способ.
Мы должны стремиться к постоянному времени, или O(1), так как это золотой стандарт для поиска в целом. Но как нам достичь этой цели?
Умное решение
К счастью, есть алгоритм, который помогает нам быстро находить и отслеживать максимум стека по мере его создания. Этот алгоритм показан в коде Ruby ниже:
class Stack
def initialize
@stack = []
@max_stack = [] # a second stack!
end
def push(val)
@stack.push(val)
if @max_stack.empty? || val > peek_max
@max_stack.push(val)
end
end
def pop
last = @stack.pop
@max_stack.pop if last == peek_max
end
def peek(index)
raise ArgumentError unless ([email protected]).include?(index)
@stack[index]
end
def peek_max
@max_stack[-1]
end
def inspect
@stack
end
def max
peek_max
end
end
Этот алгоритм на самом деле основан на использовании двухстеков: stack и max_stack.stack отслеживают целые числа, а max_stack отслеживает максимальные значения при построении стека.
Когда мы нажимаем на stack и обнаруживаем, что переданное значение больше, чем значение, расположенное вверху max_stack, мы также нажимаем это значение на max_stack.
Когда мы извлекаем из stack и обнаруживаем, что извлеченное значение совпадает со значением, расположенным вверху max_stack, мы также извлекаем последнее значение из max_stack. Значение должно быть добавлено в оба стека вместе, поэтому они должны быть удалены вместе.
Наконец, получить максимальное значение стека — это просто посмотреть на самое верхнее значение max_stack с помощью метода peek_max. Нам удалось найти максимум за время O(1) простым поиском!
Вывод
Как и все алгоритмы, этот алгоритм «двойного стека» не идеален. Предполагается, что стек изначально пуст, что позволяет нам отслеживать максимальное значение по мере создания стека. Если стек уже инициализирован значениями и мы еще не отслеживаем максимальное значение, мы должны сделать одно из следующих действий:
- Перестройте стек, создав стек максимальных значений, поскольку обычный стек перестраивается.
- Используйте метод max в «наивном» решении или другой метод, не основанный на построении стека.
Кроме того, при использовании алгоритма двойного стека возрастает сложность пространства, поскольку нам нужен совершенно новый стек для отслеживания максимальных значений. Вам решать, стоит ли функциональность O(1) push, pop и max lookup дополнительного необходимого пространства.
Тем не менее, как и все алгоритмы, этот, безусловно, полезно держать в наборе инструментов вашего программиста.
Предоставлено Interview Cake.
Подскажу сперва идею. Сделайте стек в котором хранятся как значения, так и максимумы. Например:
команда стек результат
pop [] error
pop [] error
push 4 [(4, 4)]
push -5 [(4, 4), (-5, 4)]
push 7 [(4, 4), (-5, 4), (7, 7)]
pop [(4, 4), (-5, 4)]
pop [(4, 4)]
get_max [(4, 4)] 4
pop []
get_max [] None
Как записывать и использовать максимумы догадайтесь сами.
P.S. Пристально поглядев на условия можно понять, что первое значение из пары не используется. То есть вам достаточно хранить только максимумы в стеке. Вот так:
команда стек результат
pop [] error
pop [] error
push 4 [4]
push -5 [4, 4]
push 7 [4, 4, 7]
pop [4, 4]
pop [4]
get_max [4] 4
pop []
get_max [] None
Стек избыточен в этой конкретной реализации: он хранит и значения и максимумы. Зато у него нормальный интерфейс:
class StackMaxEffective:
def __init__(self):
self.stack_ = []
def __bool__(self):
return bool(self.stack_)
def push(self, item):
if self.stack_:
new_max = max(item, self.stack_[-1][1])
else:
new_max = item
self.stack_.append((item, new_max))
def pop(self):
return self.stack_.pop()[0]
def get_max(self):
return self.stack_[-1][1]
s = StackMaxEffective()
for _ in range(int(input())):
cmd = input().split()
if cmd[0] == 'pop':
if s:
s.pop()
else:
print('error')
if cmd[0] == 'push':
s.push(int(cmd[1]))
if cmd[0] == 'get_max':
if s:
print(s.get_max())
else:
print('None')
