GetMin () колдогон стекти O (1) убакытта жана O (1) кошумча мейкиндикте иштеп чыгыңыз  


Кыйынчылык деңгээли жеңил
Көп суралган Adobe Amazon Factset Flipkart Goldman Sachs GreyOrange Кулиза Microsoft Paytm Publicis Sapient SAP Snapdeal VMware
чөмөлө

GetMin () колдогон стекти O (1) убакытта жана O (1) кошумча мейкиндикте иштеп чыгыңыз. Ошентип атайын чөмөлө маалымат структурасы стектин бардык аракеттерин колдоого тийиш -

  • void push ()
  • int pop ()
  • bool isFull ()
  • bool 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 () функциясында, учурдагы элемент минималдуу элементтен аз болсо, биз аны жаңыртабыз.

ошондой эле
Продукциянын субаррейси

Algorithm  

  1. Түзүмдү баштоо newStack жана функцияны түзүү түртүү () анда бүтүн санды параметр катары кабыл алат.
  2. Стек бош экендигин текшерип, сактаңыз бүтүн мин өзгөрмөсүндө бүтүн сандын ичине киргизип, кайтып келиңиз.
  3. Эгерде бүтүн сан минден кем болсо, стекке 2 * x - min киргизип, минди x катары жаңыртыңыз.
  4. Толугу менен стекке түртсөңүз болот.
  5. Pop () функциясын түзүңүз. Стек бош экендигин текшерип, “Стек бош” деп басып чыгып, кайтып келиңиз.
  6. Башка элемент стектин жогору жагындагы t өзгөрмөсүндө сакталат жана үстүңкү элементти стектен поп / алып салат.
  7. T мин минутан кем экендигин текшерип, мин 2 * мин - t деп жаңыртыңыз.
  8. Башка басып чыгаруу t.
  9. GetMin () функциясын түзүп, стек бош экендигин текшериңиз “Stack is empty”.
  10. Башкасы минималдуу элементти кайтарып берет.

коду  

MinStack үчүн C ++ программасы

#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

Комплекстик анализ  

Убакыт татаалдыгы

O (1) бардык операциялар туруктуу убакытта жүргүзүлүп жаткандыктан, ар бир операция үчүн.

ошондой эле
Жиптин ичине киргизилген парентизмдин максималдуу тереңдигин табыңыз

Космостун татаалдыгы

O (1) анткени биз туруктуу көмөкчү мейкиндикти колдонуп жатабыз. Киргизүүнү сактоо үчүн боштук алгоритмдин мейкиндиктин татаалдыгына байланыштуу болбойт.