Min Stack Leetcode Həlli

Problem bəyanat

Dizayn a qalaq push, pop, top və daimi elementdə minimum elementi almağı dəstəkləyən.

push (x) - x elementini yığına itələyin.
pop () - Yığının üstündəki elementi silir.
top () - Üst elementi əldə edin.
getMin () - Minimum elementi yığında alın.

Qeyd: Metodlar pop, top və getMin əməliyyatları həmişə boş olmayan yığınlarda çağırılacaq.

misal

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

-3
0
-2

Explanation:

MinStack minStack = yeni MinStack ();
minStack.push (-2);
minStack.push (0);
minStack.push (-3);
minStack.getMin (); // qayıt -3
minStack.pop ();
minStack.top (); // qayıt 0
minStack.getMin (); // qayıt -2

Yanaşma

Yığın bir elementi asanlıqla sonunda itələyə biləcəyimiz və son daxil edilmiş elementə asanlıqla daxil ola biləcəyimiz və ya açdığımız bir məlumat quruluşudur. Bu əməliyyatlar yığında O (1) vaxtında olur. Ancaq bu problemdə, yığındakı minimum elementi və O (1) vaxtında geri götürə bilməli olan əlavə bir getMin funksiyası yaratmalıyıq.

Beləliklə, bu məlumat quruluşunu dizayn etmək üçün açıq bir şəkildə əsas məlumat quruluşu olaraq yığını istifadə edəcəyik, amma əlavə bir alqoritm əlavə etməliyik ki, daimi elementi minimum vaxtda əldə edə bilək.

Bunun üçün bir nümunə görək. Bu elementləri sıraya yığmaq lazım olduğunu düşünək:
5 6 4 7 5 3 və sonra yaratmağa başlayın.

Pin

Cari minimum olan elementi açdıqda yeni minimumun itələmədən əvvəl olduğu ilə eyni olduğunu müşahidə edə bilərik. Beləliklə, əvvəlki minimum elementlərin hamısını bu günə qədər bilməliyik ki, mövcud minimum elementi O (1) vaxtında çıxardıqdan sonra minimumu əldə edək.

Bunun üçün yalnız əsas yığının minimum elementini (əncirdə yaşıl rənglə təmsil olunur) saxlayacaq başqa bir yığını istifadə edə bilərik. Beləliklə, minimum yığının üst elementi mövcud minimum elementi izah edəcəkdir.

Bir elementin yerləşdirilməsi və ya çıxarılması zamanı min yığını aşağıdakı kimi yeniləyəcəyik:

• Yeni itələnmiş element cari minimumdan az və ya bərabərdirsə, bu elementi cari minimumu yeniləmək üçün də min yığına basırıq.
• Atılan element cari minimuma bərabərdirsə, onda cari minimumu yeniləmək üçün bu elementi min yığından çıxarırıq.

Həyata keçirilməsi

Min Stack Leetcode Həlli üçün C ++ Proqramı

#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 Solution üçün Java Proqramı

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 Solution üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (1): Bütün əməliyyatlar üçün O (1). Bildiyimiz kimi yığın təkan, pop və üst üçün davamlı vaxt tələb edir. GetMin üçün bu funksiyanı daim davamlı işləməyi təmin edən başqa bir yığın istifadə etdik.

Kosmik Mürəkkəblik 

O (n): Ən pis vəziyyətdə bütün əməliyyatlar itələyicidir, bu səbəbdən kosmik mürəkkəblik O (n) olur.