Min Stack


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon Блумберг Пойтахт Яке аз DBOI Бонки олмонӣ Голдман Sachs Google Microsoft Oracle Озмоишгоҳҳои Walmart
лоиҳа тӯда

Дар min stack problem мо бояд тарроҳӣ кунем яхдон барои самаранок иҷро кардани вазифаҳои зерин,
тела додан (х) -> Элементи хро ба анбор тела диҳед
поп () -> Ашёро дар болои стака тоза мекунад
боло () -> Элементро дар болои стек баргардонед
getMin () -> Ҳадди аққали унсури дар стак мавҷудбударо баргардонед

мисол

Қайд:
Тугмачаи -2
0 -ро пахш кунед
Минро гиред
Тугмачаи -3
Поп
боло
Минро гиред
Натиҷа:
-2
0
-2

Алгоритми Min Stack

Усули push, pop ва top ба стеки муқаррарӣ монанд аст, аммо барои ба даст овардани ҳадди аққали унсури дар стак мавҷудбуда мо боз як стекро истифода мебарем, ки арзиши камтарини онро то ҳар як унсур нигоҳ медорад.

Бигзор стеки аввал st ва дуввум minSt бошанд, пас

тела додан (х)

  1. Х-ро ба стек стек тела диҳед.
  2. Агар minSt холӣ бошад ё болои minSt аз x калонтар бошад x ба minSt.
  3. Боз як бори дигар болои minSt-ро ба minSt тела диҳед.

Мураккабии вақт =О (1) 
Мураккабии фазо =О (1)

поп ()

Элементро аз stack stack ва инчунин аз stack minSt кашед.

Мураккабии вақт =О (1) 
Мураккабии фазо =О (1)

боло ()

Бозгаштан болои стек стек.

Мураккабии вақт =О (1) 
Мураккабии фазо =О (1)

getMin ()

Баргардонидани болои анбора minSt.

Мураккабии вақт =О (1) 
Мураккабии фазо =О (1)

Умуман мураккабии фазо = O (n) 
ки дар он n миқдори максималии элементҳое, ки дар як вақт ба стака тела дода мешаванд.

Шарҳи Min Stack

Намунаи дар боло овардаро дида мебароем,
Оғоз кардани ду стек ва minSt.
st = null ва minSt = null

  1. Пахш (-2)
    st = (-2) ва minSt = (-2)
  2. 0 -ро пахш кунед
    st = 0 -> (-2) ва minSt = (-2) -> (-2)
  3. getMin
    Болои minSt = (-2), бозгашт (-2)
  4. Пахш (-3)
    st = (-3) -> 0 -> (-2) ва minSt = (-3) -> (-2) -> (-2)
  5. Поп
    st = 0 -> (-2) ва minSt = (-2) -> (-2)
  6. боло
    Болои стек стакан 0 аст, баргаштан 0.
  7. getMin
    Болоии стакаи minSt (-2), баргаштан (-2) аст.

Барои тавзеҳ ба тасвири зер нигаред.

Min Stack

Кодекси JAVA барои Min Stack

import java.util.Stack;

public class MinStack {
    private static Stack<Integer> st;
    private static Stack<Integer> minSt;

    private static void push(int x) {
        // Push x to stack st
        st.push(x);
        // If minSt is empty or if top of minSt is greater than x push x to minSt.
        if (minSt.isEmpty() || minSt.peek() > x) {
            minSt.push(x);
        } else {
            // Else push top of minSt to minSt again.
            minSt.push(minSt.peek());
        }
    }

    private static void pop() {
        // Pop element from st and minSt
        st.pop();
        minSt.pop();
    }
    
    private static int top() {
        // Return top of st
        return st.peek();
    }
    
    private static int getMin() {
        // Return top of minSt
        return minSt.peek();
    }

    public static void main(String[] args) {
        // Initialise st and minSt
        st = new Stack<>();
        minSt = new Stack<>();

        // Example
        push(-2);
        push(0);
        System.out.println(getMin());
        push(-3);
        pop();
        System.out.println(top());
        System.out.println(getMin());
    }
}
-2
0
-2

C ++ Code барои Min Stack

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

stack<int> st;
stack<int> minSt;

void push(int x) {
    // Push x to stack st
    st.push(x);
    // If minSt is empty or if top of minSt is greater than x push x to minSt.
    if (minSt.empty() || minSt.top() > x) {
        minSt.push(x);
    } else {
        // Else push top of minSt to minSt again.
        minSt.push(minSt.top());
    }
}

void pop() {
    // Pop element from st and minSt
    st.pop();
    minSt.pop();
}

int top() {
    // Return top of st
    return st.top();
}

int getMin() {
    // Return top of minSt
    return minSt.top();
}

int main() {
    // Example
    push(-2);
    push(0);
    cout<<getMin()<<endl;
    push(-3);
    pop();
    cout<<top()<<endl;
    cout<<getMin()<<endl;
    
    return 0;
}
-2
0
-2

Адабиёт