Дизајнирајте оџак што поддржува getMin () во O (1) време и O (1) дополнителен простор


Ниво на тешкотија Лесно
Често прашувано во Adobe Амазон Факти Flipkart Голдман Сакс GreyOrange Кулиза Мајкрософт Исплата Публицис Сапиент САП Snapdeal VMware
Магацинот

Дизајнирајте оџак што поддржува getMin () во O (1) време и O (1) дополнителен простор. Така специјалното магацинот структурата на податоците мора да ги поддржува сите операции на оџакот како -

  • неважечки притисок ()
  • int поп ()
  • bool isFull ()
  • bool е Празна ()

во постојано време. Додадете дополнителна операција getMin () за да ја вратите минималната вредност во специјалниот оџак во константно време и О (1) дополнителен простор.

Дизајнирајте оџак што поддржува getMin () во O (1) време и O (1) дополнителен простор

пример

push(30)
push(20)
push(10)
getMin()
pop()
getMin()
Minimum element : 10
Popped element : 10
Minimum element : 20
push(500)
push(50)
push(5)
getMin()
pop()
getMin()
Minimum element : 5
Popped element : 5
Minimum element : 50

Математички / набудуван метод за спроведување на minStack

Во овој пристап го ажурираме минималниот елемент како -

Во функцијата push () ако цел број што треба да се турка е помал од минималниот елемент што го вметнуваме двапати од тој цел број минус минимален елемент во оџакот, кој секогаш ќе биде помал од дадениот цел број како -

  • даден цел број <минимален елемент што значи даден цел број - минимален елемент <0
  • // Додавање на даден цел број на обете страни
  • даден цел број - минимален елемент + даден цел број <0 + даден цел број
  • 2 * даден цел број - минимален елемент <даден цел број
  • Можеме да заклучиме 2 * даден цел број - минимален елемент <нов минимален елемент

така, додека ќе се појави овој елемент, тој ќе биде помал од минималниот, затоа ќе го ажурираме минималниот елемент.

Слично на тоа, во функцијата поп (), ако тековниот елемент е помал од минималниот елемент, ќе го ажурираме.

Алгоритам

  1. Иницијализирај структура newStack и креирајте функција притисни () во него што прифаќа цел број како параметар.
  2. Проверете дали оџакот е празен, чувајте го број во променлива мин, вметнете го целиот број во стек и вратете го.
  3. Друго ако цел број е помал од мин вметнете 2 * x - мин во стек и ажурирајте го мин како x.
  4. Друго, туркај го целиот број во магацинот.
  5. Создадете ја функцијата поп (). Проверете дали оџакот е празен. „Стак е празен“ и вратете се.
  6. Друго чувајте го елементот на врвот на оџакот во променлива t и поп / отстранете го горниот елемент од оџакот.
  7. Проверете дали t е помалку од мин. Мин. За печатење и ажурирајте го мин. За 2 * min - t.
  8. Друго печатење т.
  9. Создадете ја функцијата getMin () и проверете дали оџакот е празен.
  10. Друго вратете го минималниот елемент.

Код

Програма C ++ за minStack

#include <bits/stdc++.h> 
using namespace std; 
  
struct newStack{ 
    stack<int> s; 
    int min; 
  
    void getMin(){ 
        if(s.empty()){ 
            cout<<"Stack is empty\n"; 
        }
        else{
            cout<<"Minimum element : "<<min<<"\n"; 
        }    
    } 
  
    void pop(){ 
        if(s.empty()){ 
            cout<<"Stack is empty\n"; 
            return; 
        } 
  
        cout<<"Popped element : "; 
        int t = s.top(); 
        s.pop(); 
  
        if(t<min){ 
            cout<<min<< "\n"; 
            min = 2*min - t; 
        } 
  
        else{
            cout<<t<< "\n";
        }    
    } 
  
    void push(int x){ 
        if(s.empty()){ 
            min = x; 
            s.push(x); 
            return; 
        } 
  
        if(x < min){ 
            s.push(2*x - min); 
            min = x; 
        } 
  
        else{
           s.push(x);
        }   
    } 
}; 
 
int main(){
    newStack s; 
    
    s.push(30);
    s.push(20);
    s.push(10);
    s.getMin();
    s.pop();
    s.getMin();
  
    return 0; 
}
Minimum element : 10
Popped element : 10
Minimum element : 20

Јава програма за minStack

import java.util.*; 
  
class newStack{ 
    Stack<Integer> s; 
    Integer min; 
  
    newStack(){ 
        s = new Stack<Integer>(); 
    } 
  
    void getMin(){ 
        if(s.isEmpty()) 
            System.out.println("Stack is empty"); 
  
        else{
            System.out.println("Minimum element : " + min);
        }    
    } 
  
    void pop(){ 
        if (s.isEmpty()){ 
            System.out.println("Stack is empty"); 
            return; 
        } 
  
        System.out.print("Popped element : "); 
        Integer t = s.pop(); 
  
        if(t<min){ 
            System.out.println(min); 
            min = 2*min - t; 
        } 
  
        else{
            System.out.println(t);
        }    
    } 
  
    void push(Integer x){ 
        if(s.isEmpty()){ 
            min = x; 
            s.push(x); 
            return; 
        } 
  
        if(x<min){ 
            s.push(2*x - min); 
            min = x; 
        } 
  
        else{
            s.push(x); 
        }    
    } 
}; 
  
public class Main{ 
    public static void main(String[] args){ 
        newStack s = new newStack(); 
        
        s.push(30);
        s.push(20);
        s.push(10);
        s.getMin();
        s.pop();
        s.getMin();
        
    } 
}
Minimum element : 10
Popped element : 10
Minimum element : 20

Анализа на сложеност

Временска комплексност

О (1) за секоја операција, бидејќи сите операции се прават во постојано време.

Комплексноста на просторот

О (1) бидејќи користиме дополнителен помошен простор. Просторот потребен за зачувување на влезот не смета за сложеноста на просторот на алгоритмот.