Ҳалли Min Stack Leetcode


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

Изҳороти мушкилот

Тарроҳӣ a яхдон ки пушту, поп, боло ва ҷустуҷӯи унсури ҳадди ақалро дар вақти доимӣ дастгирӣ мекунад.

тела додан (х) - Элементи хро ба анбора пахш кунед.
pop () - Элементро дар болои стака тоза мекунад.
top () - Элементи болоиро гиред.
getMin () - Ҷустуҷӯи ҳадди аққали элемент дар стака.

Эзоҳ: Усулҳои амалиётҳои поп, 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) дар стек ба амал меоянд. Аммо дар ин масъала мо бояд функсияи getMin изофӣ созем, ки битавонад унсури ҳадди ақалро дар стак ва инчунин дар вақти O (1) ҷустуҷӯ кунад.

Аз ин рӯ, барои таҳияи ин сохтори додаҳо, мо албатта стекро ҳамчун сохтори асосии додаҳо истифода хоҳем кард, аммо мо бояд ба он алгоритми изофӣ илова кунем, то битавонем унсури ҳадди ақалро дар вақти доимӣ ба даст орем.

Барои ин, биёед намунаеро бубинем. Фарз мекунем, ки мо бояд ин унсурҳоро ба тартиб бо навбат дохил кунем:
5 6 4 7 5 3, ва он гоҳ оғоз ба поп.

Ҳалли Min Stack Leetcode

Мо метавонем мушоҳида кунем, ки вақте ки мо унсуреро, ки низ ҳадди аққал ҷорӣ аст, пас минимуми нав ҳамон тавре аст, ки пеш аз пахш кардан буд. Пас, мо бояд то имрӯз дар бораи ҳамаи унсурҳои минималии қаблӣ маълумот дошта бошем, то пас аз бартараф кардани унсури минималии ҳозира дар вақти O (1) ҳадди ақалро гирем.

Барои ин, мо метавонем стеки дигарро истифода барем, ки танҳо ҷузъи минималии (бо ранги сабз дар анҷир ифодаёфта) стеки асосиро нигоҳ медорад. Ҳамин тавр унсури болоии минималии стака унсури ҳадди ақали ҷориро нақл мекунад.

Ҳангоми дохилкунӣ ё нест кардани унсур мо мини стакаро ба тариқи зерин навсозӣ мекунем:

  • Агар унсури нави тела додашуда аз ҳадди ақали ҳозира камтар ё ба он баробар бошад, пас мо ин элементро ба min stack меандозем, то ҳадди ақали ҷориро навсозӣ кунем.
  • Агар унсури партофташуда ба ҳадди ақали ҷорӣ баробар бошад, пас мо ин унсурро аз минаи стака тоза карда, ҳадди ақали ҷориро навсозӣ мекунем.

татбиќи

Барномаи C ++ барои ҳалли Min Stack Leetcode

#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 Solution

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): O (1) барои ҳамаи амалиётҳо. Тавре ки мо медонем, стак барои пахш, поп ва боло вақти доимӣ мегирад. Барои getMin мо стаки дигарро истифода кардем, ки ин функсияро низ дар вақти доимӣ кор мекунад.

Мураккабии фазо 

O (n): Дар ҳолати бадтарин, тамоми амалиёт пешравӣ аст, аз ин рӯ мураккабии фазо O (n) мебошад.