Стекро таҳия кунед, ки getMin () -ро дар вақти O (1) ва фазои иловагии O (1) -ро дастгирӣ кунад


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Adobe Amazon Factset Flipkart Голдман Sachs GreyOrange Кулиза Microsoft Пардохт Publicis Sapient SAP Snapdeal VMware
тӯда

Стекро таҳия кунед, ки getMin () -ро дар вақти O (1) ва O (1) фазои иловагиро дастгирӣ кунад. Ҳамин тариқ махсус яхдон сохтори маълумот бояд ҳамаи амалҳои стекро дастгирӣ кунад, ба монанди -

  • такони ботил ()
  • int pop ()
  • матниқӣ isFull ()
  • матниқӣ isEmpty ()

дар вақти доимӣ. Барои баргардонидани арзиши минималӣ дар стеки махсус дар вақти доимӣ ва O (1) фазои иловагӣ амалиёти иловагии getMin () -ро илова кунед.

Стекро таҳия кунед, ки 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 * адади додашуда хулоса барорем - унсури ҳадди ақалл <унсури ҳадди ақали нав

пас ҳангоми баровардани ин унсур он аз унсури минималӣ камтар хоҳад буд, бинобар ин мо унсури ҳадди ақалро нав хоҳем кард.

Ба ҳамин монанд, дар функсияи pop (), агар унсури ҷорӣ аз унсури минималӣ камтар бошад, мо онро навсозӣ мекунем.

Алгоритм

  1. Сохторро оғоз кунед newStack ва эҷод кардани функсия Тела() дар он, ки бутунро ҳамчун параметр қабул мекунад.
  2. Санҷед, ки анбора холӣ аст, нигоҳ доред ҳамаҷониба дар тағирёбандаи дақ, ададро ба стек дохил кунед ва баргардед.
  3. Дигар, агар адад аз min камтар бошад, 2 * x - min дар стек дохил кунед ва min -ро x x навсозӣ кунед.
  4. Вагарна бутуни бутунро дар стек пахш кунед.
  5. Функсияи pop () -ро эҷод кунед. Санҷед, ки стек холӣ аст Чопи "Stack is empty" ва бозгашт.
  6. Дигаре унсурро дар болои стек дар тағирёбандаи t нигоҳ медорад ва унсури болоро аз стак поп / хориҷ кунед.
  7. Санҷед, ки t камтар аз дақиқа чоп кардани дақиқа аст ва дақ аз 2 * дақ - t навсозӣ кунед.
  8. Дигар чоп т.
  9. Функсияи getMin () -ро эҷод кунед ва холӣ будани анбораро тафтиш кунед "Stack is empty".
  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

Барномаи Java барои 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) зеро мо фазои ёридиҳандаи доимиро истифода мебарем. Фосилае, ки барои нигоҳ доштани вуруд зарур аст, ба мураккабии фазоии алгоритм ба ҳисоб гирифта намешавад.