מינימום פתרון Leetcode פתרון


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית תפוח עץ בלומברג קפיטל אחד מיקרוסופט אורקל
עיצוב לערום

הצהרת בעיה

עיצוב א לערום התומך בדחיפה, פופ, למעלה, ואחזור האלמנט המינימלי בזמן קבוע.

לדחוף (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) בערימה. אבל בבעיה זו עלינו לבצע פונקציה נוספת getMin שאמורה להיות מסוגלת להחזיר את האלמנט המינימלי בערימה ושגם בזמן O (1).

אז כדי לתכנן את מבנה הנתונים הזה ברור שנשתמש בערימה כמבנה נתונים ראשי, אך עלינו להוסיף לו אלגוריתם נוסף כדי שנוכל להשיג אלמנט מינימלי בזמן קבוע.

לשם כך, בואו נראה דוגמה. נניח שעלינו להוסיף את האלמנטים האלה בערימה לפי הסדר:
5 6 4 7 5 3, ואז התחל לצוץ.

מינימום פתרון Leetcode פתרון

אנו יכולים לראות שכאשר אנו מקפיצים את האלמנט שהוא גם המינימום הנוכחי, המינימום החדש זהה לזה שהיה לפני שדחפנו אותו. אז עלינו להכיר את כל האלמנטים המינימליים הקודמים עד כה כדי שנוכל לאחזר את המינימום לאחר הסרת האלמנט המינימלי הנוכחי בזמן O (1).

לשם כך אנו יכולים להשתמש בערימה אחרת שתאחסן רק את האלמנט המינימלי (המיוצג עם צבע ירוק בתא) של הערימה הראשית. אז האלמנט העליון של ערימת המינימום יגיד את אלמנט המינימום הנוכחי.

במהלך הכנסה או הסרה של אלמנט נעדכן את מחסנית הדקות כמפורט להלן:

  • אם האלמנט הדחוף החדש קטן או שווה למינימום הנוכחי, אנו דוחפים את האלמנט הזה למחסנית min כדי לעדכן את המינימום הנוכחי.
  • אם האלמנט המופץ שווה למינימום הנוכחי, אז אנו מוציאים את האלמנט הזה מערימה המינימלית כדי לעדכן את המינימום הנוכחי.

יישום

תוכנית C ++ לפתרון Minet Leetcode Solution

#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

מורכבות זמן

O (1): O (1) לכל הפעולות. כידוע מחסנית לוקח זמן קבוע לדחיפה, פופ, ומעלה. עבור getMin השתמשנו בערימה אחרת שהופכת פונקציה זו גם לעבוד בזמן קבוע.

מורכבות בחלל 

O (n): במקרה הגרוע כל הפעולה היא דחיפה, ולכן מורכבות החלל היא O (n).