کم سے کم اسٹیک


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایمیزون بلومبرگ کیپٹل ایک DBOI ڈوئچے بینک گولڈمین سیکس گوگل مائیکروسافٹ اوریکل والمارٹ لیبز
ڈیزائن اسٹیک

کم سے کم اسٹیک مسئلہ میں ہمیں ڈیزائن کرنا ہوگا ڈھیر لگانا مندرجہ ذیل افعال کو موثر انداز میں نافذ کرنے کے لئے ،
دھکا (X) -> ایک عنصر کو اسٹیک پر پش کریں
پاپ () -> اسٹیک کے اوپری حصے میں آئٹم کو ہٹاتا ہے
اوپر () -> عنصر کو اسٹیک کے اوپری حصے میں لوٹائیں
getMin () -> اسٹیک میں موجود کم سے کم عنصر کو واپس کریں

مثال کے طور پر

ان پٹ:
پش -2
0 دھکا
کم سے کم حاصل کریں
پش -3
پاپ
اوپر
کم سے کم حاصل کریں
: پیداوار
-2
0
-2

منی اسٹیک کے لئے الگورتھم

پش ، پاپ ، اور ٹاپ طریقہ ایک عام اسٹیک کی طرح ہے ، لیکن اسٹیک میں موجود کم سے کم عنصر حاصل کرنے کے لئے ہم ایک اور اسٹیک استعمال کرتے ہیں جو ہر عنصر تک کم سے کم قیمت کو محفوظ کرتا ہے۔

پہلے اسٹیک کو سینٹ اور دوسرا اسٹیک منسٹ ہو ، پھر

دھکا (X)

  1. اسٹیک سینٹ پر ایکس کو دبائیں۔
  2. اگر minSt خالی ہے یا اگر minSt کا اوپری حص xہ x x x x سے minStSt سے زیادہ ہے۔
  3. ورنہ minSt کے سب سے اوپر کو پھر سے minSt پر دبائیں۔

وقت کی پیچیدگی =O (1) 
خلائی پیچیدگی =O (1)

پاپ ()

اسٹیک سینٹ سے اور اسٹیک منسٹسٹ سے بھی عنصر پوپ کریں۔

وقت کی پیچیدگی =O (1) 
خلائی پیچیدگی =O (1)

اوپر ()

اسٹیک کی چوٹی واپس کریں۔

وقت کی پیچیدگی =O (1) 
خلائی پیچیدگی =O (1)

getMin ()

اسٹیک minSt کے سب سے اوپر واپس.

وقت کی پیچیدگی =O (1) 
خلائی پیچیدگی =O (1)

مجموعی طور پر خلائی پیچیدگی = O (n) 
جہاں n ایک وقت میں اسٹیک میں ڈالے جانے والے عناصر کی زیادہ سے زیادہ تعداد ہے۔

من اسٹیک کے لئے وضاحت

مندرجہ بالا مثال پر غور کریں ،
دو اسٹیک سینٹ اور منٹ ٹائم کا آغاز کریں۔
st = null and minSt = null

  1. پش (-2)
    st = (-2) اور minSt = (-2)
  2. 0 دھکا
    st = 0 -> (-2) اور منٹ اسٹ = (-2) -> (-2)
  3. getMin
    minSt = (-2) کا سب سے اوپر ، واپسی (-2)
  4. پش (-3)
    st = (-3) -> 0 -> (-2) اور منٹ اسٹ = (-3) -> (-2) -> (-2)
  5. پاپ
    st = 0 -> (-2) اور منٹ اسٹ = (-2) -> (-2)
  6. اوپر
    اسٹیک کا سب سے اوپر 0 ہے ، 0 واپس۔
  7. getMin
    اسٹیک منسٹاسٹی کا سب سے اوپر (-2) ، واپسی (-2) ہے۔

وضاحت کے لئے نیچے دی گئی تصویر دیکھیں۔

کم سے کم اسٹیک

جاوا کوڈ برائے من اسٹیک

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 ++ کوڈ

#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

حوالہ جات