דיזיין אַ אָנלייגן וואָס שטיצט געטמין () אין אָ (1) צייט און אָ (1) עקסטרע פּלאַץ


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַדאָובי אַמאַזאָן פאַקסעט פליפּקאַרט גאָלדמאַן סאַקס גריי אָראַנדזש Kuliza מייקראָסאָפֿט Paytm פּובליסיס סאַפּיענט זאַפט סנאַפּדעאַל וומוואַרע
אָנלייגן

דיזיין אַ אָנלייגן וואָס שטיצט געטמין () אין אָ (1) צייט און אָ (1) עקסטרע פּלאַץ. אזוי דער ספּעציעל stack דאַטן סטרוקטור מוזן שטיצן אַלע די אַפּעריישאַנז פון דעם אָנלייגן ווי -

  • פּאָסל שטופּן ()
  • ינט פּאָפּ ()
  • באָאָל איז פול ()
  • באָאָל איז ליידיק ()

אין קעסיידערדיק צייַט. לייג אַן נאָך אָפּעראַציע געטמין () צו צוריקקומען די מינימום ווערט אין ספּעציעל אָנלייגן אין קעסיידערדיק צייט און אָ (1) עקסטרע פּלאַץ.

דיזיין אַ אָנלייגן וואָס שטיצט געטמין () אין אָ (1) צייט און אָ (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

אין דעם צוגאַנג, מיר דערהייַנטיקן די מינימום עלעמענט ווי -

אין שטופּן () פונקציאָנירן אויב די גאַנץ נומער צו זיין פּושט איז ווייניקער ווי די מינימום עלעמענט, מיר ינסערטאַד צוויי מאָל פון די גאַנץ נומער מינוס מינימום עלעמענט אין סטאַק, וואָס וועט שטענדיק זיין קלענערער ווי די געגעבן גאַנץ נומער ווי -

  • געגעבן ינטאַדזשער <מינימום עלעמענט וואָס מיטל געגעבן ינטאַדזשער - מינימום עלעמענט <0
  • // אַדדינג אַ גאַנץ נומער פון ביידע זייטן
  • געגעבן ינטאַדזשער - מינימום עלעמענט + געגעבן ינטאַדזשער <0 + געגעבן ינטאַדזשער
  • 2 * געגעבן ינטאַדזשער - מינימום עלעמענט <געגעבן ינטאַדזשער
  • מיר קענען פאַרענדיקן 2 * געגעבן ינטאַדזשער - מינימום עלעמענט <נייַ מינימום עלעמענט

אַזוי בשעת פּאַפּינג דעם עלעמענט עס וועט זיין ווייניקער ווי די מינימום עלעמענט, און מיר דערהייַנטיקן די מינימום עלעמענט.

סימילאַרלי, אין פּאָפּ () פונקציע, אויב די קראַנט עלעמענט איז ווייניקער ווי די מינימום עלעמענט, מיר דערהייַנטיקן עס.

אַלגאָריטהם

  1. יניטיאַליזירן אַ סטרוקטור נעווסטאַקק און שאַפֿן אַ פונקציע שטופּן () אין עס וואָס אַקסעפּץ אַ גאַנץ נומער ווי אַ פּאַראַמעטער.
  2. קאָנטראָלירן אויב די אָנלייגן איז ליידיק ינטעגער אין אַ בייַטעוודיק מין, אַרייַן די ינטאַדזשער אין אָנלייגן און צוריקקומען.
  3. אַנדערש אויב די ינטאַדזשער איז ווייניקער ווי מין אַרייַן 2 * X - מין אין אָנלייגן און דערהייַנטיקן MIN ווי X.
  4. אַנדערש שטופּן די ינטאַדזשער אין אָנלייגן.
  5. שאַפֿן די פונקציע פּאָפּ (). טשעק אויב אָנלייגן איז ליידיק דרוק "אָנלייגן איז ליידיק" און צוריקקומען.
  6. אַנדערש קראָם די עלעמענט אין שפּיץ פון אָנלייגן אין אַ בייַטעוודיק ה און קנאַל / אַראָפּנעמען די שפּיץ עלעמענט פֿון אָנלייגן.
  7. קאָנטראָלירן צי ה איז ווייניקער ווי מין דרוקן מין און דערהייַנטיקן מין ווי 2 * מין - ה.
  8. אלזא דרוק ט.
  9. שאַפֿן די פונקציע געטמין () און קאָנטראָלירן צי דער אָנלייגן איז ליידיק דרוקן "אָנלייגן איז ליידיק".
  10. אַנדערש צוריקקומען די מינימום עלעמענט.

קאָדעקס

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 פּראָגראַם פֿאַר מינסטאַקק

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) ווייַל מיר נוצן קאַנטאַנט אַגזיליערי פּלאַץ. די פּלאַץ פארלאנגט צו קראָם די אַרייַנשרייַב איז ניט גערעכנט ווי די פּלאַץ קאַמפּלעקסיטי פון אַלגערידאַם.