Minet Stack Leetcode шешімі  


Күрделілік дәрежесі оңай
Жиі кіреді Amazon алма Bloomberg Capital One Microsoft Oracle
алгоритмдер кодтау жобалау сұхбат сұхбат дайындау LeetCode LeetCodeSolutions үйме

Проблемалық мәлімдеме  

Дизайн а Стек минималды элементті тұрақты уақытта итеріп, шығарып алуды, шығаруды қолдайды.

push (x) - x элементін стекке итеріңіз.
pop () - стектің жоғарғы жағындағы элементті жояды.
top () - жоғарғы элементті алыңыз.
getMin () - минималды элементті стекке шығарып алыңыз.

Ескерту: pop, top және getMin амалдары әрқашан бос емес стектерде шақырылатын болады.

мысал

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

Түсіндіру:

MinStack minStack = жаңа MinStack ();
minStack.push (-2);
minStack.push (0);
minStack.push (-3);
minStack.getMin (); // қайтару -3
minStack.pop ();
minStack.top (); // қайтару 0
minStack.getMin (); // қайтару -2

жақындау  

Стек дегеніміз - бұл элементті соңында итеріп, сонымен қатар кірістірілген немесе соңғы енгізілген элементті ашатын мәліметтер құрылымы. Бұл операциялар стек ішінде O (1) уақытта болады. Бірақ бұл мәселеде біз минималды элементті стекке шығарып алу мүмкін болатын және тағы O (1) уақыт ішінде қосымша getMin функциясын жасауымыз керек.

Деректер құрылымын жобалау үшін біз стекті негізгі мәліметтер құрылымы ретінде қолданатынымыз анық, бірақ біз оған қосымша алгоритм қосуымыз керек, сондықтан тұрақты уақытта минималды элемент аламыз.

Бұл үшін мысалды көрейік. Біз бұл элементтерді қатарына бір қатарға салуымыз керек делік:
5 6 4 7 5 3, содан кейін пайда бола бастаңыз.

Minet Stack Leetcode шешімі

Қазіргі минимум болатын элементті шығарған кезде жаңа минимум оны итермелегенге дейінгідей болатынын байқауға болады. Сонымен, қазіргі минималды элементті O (1) уақытта алып тастағаннан кейін, минимумды алу үшін, біз осы уақытқа дейінгі барлық минималды элементтер туралы білуіміз керек.

Сондай-ақ, қараңыз
Leetcode шешімінің тіркесімдері

Ол үшін негізгі стектің тек минималды элементін (інжірде жасыл түспен бейнеленген) сақтайтын басқа стекті қолдануға болады. Сонымен, минималды стектің жоғарғы элементі ағымдағы минималды элементті айтады.

Элементті енгізу немесе жою кезінде мин стегін төмендегідей жаңартамыз:

  • Егер жаңа итерілген элемент ағымдағы минимумнан аз немесе оған тең болса, онда біз осы элементті минималды стекке итеріп, ағымдағы минимумды жаңартамыз.
  • Егер қойылған элемент ағымдағы минимумға тең болса, онда біз минималды стектен осы элементті алып тастаймыз, сонымен қатар ағымдағы минимумды жаңартамыз.

Іске асыру  

Minimum Stack Leetcode шешіміне арналған 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

Min Stack Leetcode шешіміне арналған Java бағдарламасы

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

Minet Stack Leetcode шешімінің күрделілігін талдау  

Уақыттың күрделілігі

O (1): O (1) барлық операциялар үшін. Біздің білуімізше, стек итеру, поп және үстіңгі жағы үшін тұрақты уақытты алады. GetMin үшін біз бұл функцияны тұрақты уақытта жұмыс істейтін тағы бір стек қолдандық.

Сондай-ақ, қараңыз
BST ішіндегі ең кіші элементті табыңыз (тапсырыс статистикасы БСТ бойынша)

Ғарыштың күрделілігі 

O (n): Нашар жағдайда барлық операциялар итермелейді, сондықтан ғарыштық қиындық O (n) болады.