מיני סטאַק לעעטקאָדע סאַלושאַן


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

פּראָבלעם סטאַטעמענט

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

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

באַמערקונג: מעטהאָדס פּאָפּ, שפּיץ און געטמין אָפּעראַטיאָנס וועט שטענדיק זיין גערופֿן אויף ניט-ליידיק סטאַקס.

בייַשפּיל

push(-2);
push(0);
push(-3);
getMin();
pop();
top();
getMin();
-3
0
-2

דערקלערונג:

מינסטאַקק מינסטאַקק = נייַ מינסטאַקק ();
מינסטאַקק.פּוש (-2);
מינסטאַקק.פּוש (0);
מינסטאַקק.פּוש (-3);
מינסטאַקק.געטמין (); // צוריקקומען -3
מינסטאַקק.פּאָפּ ();
מינסטאַקק.טאָפּ (); // צוריקקומען 0
מינסטאַקק.געטמין (); // צוריקקומען -2

צוגאַנג

מיר וויסן אַז אַ אָנלייגן איז אַ דאַטן סטרוקטור אין וואָס מיר קענען לייכט שטופּן אַן עלעמענט אין די סוף און אויך לייכט אַקסעס אָדער קנאַל די לעצטע ינסערטאַד עלעמענט. די אַפּעריישאַנז כאַפּאַנז אין אָ (1) מאָל אין אַ אָנלייגן. אָבער אין דעם פּראָבלעם מיר האָבן צו מאַכן אַן עקסטרע פונקציע געטמין וואָס זאָל קענען צו צוריקקריגן די מינימום עלעמענט אין דעם אָנלייגן און אַז אויך אין O (1) צייט.

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

פֿאַר דעם, לאָזן אַ ביישפּיל זען. לאָמיר רעכן מיר מוזן שטעלן די יסודות אין אָנלייגן אין סדר:
5 6 4 7 5 3, און דאַן אָנהייב פּאַפּינג.

מיני סטאַק לעעטקאָדע סאַלושאַן

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

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

בעשאַס ינסערשאַן אָדער באַזייַטיקונג פון אַן עלעמענט, מיר דערהייַנטיקן די מין סטאַק ווי אונטן:

  • אויב די נייַע פּושט עלעמענט איז ווייניקער ווי אָדער גלייַך צו די קראַנט מינימום, מיר שטופּן דעם עלעמענט אויך צו דערהייַנטיקן דעם קראַנט מינימום.
  • אויב די פּאַפּט עלעמענט איז גלייַך צו דעם קראַנט מינימום, מיר וועלן אויך באַזייַטיקן דעם עלעמענט פֿון דעם מין אָנלייגן צו דערהייַנטיקן דעם קראַנט מינימום.

ימפּלעמענטאַטיאָן

C ++ פּראָגראַם פֿאַר מין סטאַק לעעטקאָדע סאַלושאַן

#include <bits/stdc++.h>
using namespace std;

class MinStack {
public:
    stack<int> st,mn;
    
    void push(int x) 
    {
        if(st.empty() || x<=mn.top())
            mn.push(x);
        st.push(x);
    }
    
    void pop() 
    {
        if(st.top()==mn.top()) 
            mn.pop();
        st.pop();
    }
    
    int top() 
    {
        return st.top();
    }
    
    int getMin() 
    {
        return mn.top();
    }
};

int main() 
{
    MinStack* minStack = new MinStack();
    minStack->push(-2);
    minStack->push(0);
    minStack->push(-3);
    int param1 = minStack->getMin(); 
    minStack->pop();
    int param2 = minStack->top();   
    int param3 = minStack->getMin(); 
    
    cout<<param1<<endl;
    cout<<param2<<endl;
    cout<<param3<<endl;
    
    return 0; 
}
-3
0
-2

Java פּראָגראַם פֿאַר Min Stack Leetcode סאַלושאַן

import java.util.*;
class MinStack {

    Stack<Integer> st=new Stack<>();
    Stack<Integer> mn=new Stack<>();
   
    public void push(int x) 
    {
        if(st.empty() || x<=mn.peek())
            mn.push(x);
        st.push(x);
    }
    
    public void pop() 
    {
        if(st.peek().equals(mn.peek())) 
            mn.pop();
        st.pop();
    }
    
    public int top() 
    {
         return st.peek();
    }
    
    public int getMin() 
    {
        return mn.peek();
    }
}

class Rextester{

  public static void main(String args[])
    {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        int param1 = minStack.getMin(); 
        minStack.pop();
        int param2 = minStack.top();   
        int param3 = minStack.getMin(); 
        
    System.out.println(param1);
        System.out.println(param2);
        System.out.println(param3);
    }
}
-3
0
-2

קאַמפּלעקסיטי אַנאַליסיס פֿאַר Min Stack Leetcode סאַלושאַן

צייט קאַמפּלעקסיטי

אָ (1): אָ (1) פֿאַר אַלע אַפּעריישאַנז. ווי מיר וויסן סטאַק נעמט קעסיידערדיק צייט פֿאַר שטופּן, קנאַל און שפּיץ. פֿאַר GetMin, מיר האָבן געוויינט אן אנדער אָנלייגן וואָס מאכט די פֿונקציע אויך ארבעטן אין קעסיידערדיק צייט.

ספעיס קאַמפּלעקסיטי 

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