મીન સ્ટેક લેટકોડ સોલ્યુશન


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન સફરજન બ્લૂમબર્ગ કેપિટલ વન માઈક્રોસોફ્ટ ઓરેકલ
ડિઝાઇન સ્ટેક

સમસ્યા નિવેદન

ડિઝાઇન એ સ્ટેક જે પુશ, પ popપ, ટોપ અને સતત સમયમાં લઘુત્તમ તત્વને પ્રાપ્ત કરવા માટે સપોર્ટ કરે છે.

પુશ (એક્સ) - સ્ટેક પર એલિમેન્ટ એક્સ દબાણ કરો.
પ popપ () - સ્ટેકની ટોચ પરના તત્વને દૂર કરે છે.
ટોચ () - ટોચનું તત્વ મેળવો.
getMin () - સ્ટેકમાં ન્યૂનતમ તત્વ પ્રાપ્ત કરો.

નોંધ: પદ્ધતિઓ પ popપ, ટોપ અને ગેટમિન operationsપરેશંસ હંમેશાં ખાલી ન હોય તેવા સ્ટેક્સ પર કહેવામાં આવશે.

ઉદાહરણ

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

સમજૂતી:

મિનસ્ટackક મિનસ્ટackક = નવી મિનસ્ટackક ();
minStack.push (-2);
minStack.push (0);
minStack.push (-3);
minStack.getMin (); // રીટર્ન -3
minStack.pop ();
minStack.top (); // રીટર્ન 0
minStack.getMin (); // રીટર્ન -2

અભિગમ

આપણે જાણીએ છીએ કે સ્ટેક એ એક ડેટા સ્ટ્રક્ચર છે જેમાં આપણે સરળતાથી કોઈ તત્વ સરળતાથી અંતમાં આગળ ધપાવી શકીએ છીએ અને છેલ્લે દાખલ કરેલા તત્વને સરળતાથી accessક્સેસ કરી શકીએ છીએ અથવા પ popપ કરી શકીએ છીએ. આ operationsપરેશન ઓ (1) સમયથી એક સ્ટેકમાં થાય છે. પરંતુ આ સમસ્યામાં અમારે એક વધારાનું ફંક્શન ગેટમિન બનાવવું પડશે જે સ્ટેકમાં લઘુત્તમ તત્વને પુનriveપ્રાપ્ત કરવા માટે સક્ષમ હોવું જોઈએ અને તે પણ ઓ (1) સમયમાં.

તેથી આ ડેટા સ્ટ્રક્ચરને ડિઝાઇન કરવા માટે આપણે સ્ટેકનો ઉપયોગ મુખ્ય ડેટા સ્ટ્રક્ચર તરીકે કરીશું પરંતુ આપણે તેમાં કેટલાક વધારાના અલ્ગોરિધમનો ઉમેરવા પડશે જેથી આપણે સતત સમયમાં લઘુત્તમ તત્વ મેળવી શકીએ.

આ માટે, ચાલો એક ઉદાહરણ જોઈએ. ચાલો ધારો કે આપણે આ તત્વોને ક્રમમાં ગોઠવીશું:
5 6 4 7 5 3, અને પછી પpingપ કરવાનું પ્રારંભ કરો.

મીન સ્ટેક લેટકોડ સોલ્યુશન

આપણે અવલોકન કરી શકીએ છીએ કે જ્યારે આપણે એલિમેન્ટને પ popપ કરીએ છીએ જે હાલનું લઘુતમ પણ હોય છે, તો નવું ન્યૂનતમ એ દબાણ કરતા પહેલા જેવું હતું તેવું જ છે. તેથી અમારી પાસે પહેલાના તમામ લઘુત્તમ તત્વોનું જ્ nowાન હોવું આવશ્યક છે જેથી અમે ઓ (1) સમયમાં વર્તમાન લઘુત્તમ તત્વને દૂર કર્યા પછી લઘુત્તમ મેળવી શકીએ.

આ માટે આપણે બીજો સ્ટેકનો ઉપયોગ કરી શકીએ છીએ જે ફક્ત મુખ્ય સ્ટેકના ન્યૂનતમ તત્વ (અંજીરમાં લીલા રંગ સાથે રજૂ) સંગ્રહિત કરશે. તેથી ન્યૂનતમ સ્ટેકનું ટોચનું તત્વ વર્તમાન લઘુત્તમ તત્વને કહેશે.

ઘટક દાખલ કરવા અથવા કા Duringવાના સમયે, અમે નીચે પ્રમાણે મિનિ સ્ટેકને અપડેટ કરીશું:

  • જો નવું દબાણ કરાયેલ તત્વ વર્તમાન લઘુત્તમ કરતા ઓછું અથવા બરાબર છે, તો અમે વર્તમાન લઘુત્તમને અપડેટ કરવા માટે પણ આ ઘટકને મિનિટ સ્ટેકમાં દબાણ કરીએ છીએ.
  • જો પpedપ્ડ તત્વ વર્તમાન લઘુત્તમ જેટલું છે, તો પછી અમે વર્તમાન લઘુત્તમને અપડેટ કરવા માટે આ ઘટકને મિનિ સ્ટેકથી પણ દૂર કરીએ છીએ.

અમલીકરણ

મીન સ્ટેક લેટકોડ સોલ્યુશન માટે સી ++ પ્રોગ્રામ

#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

મીન સ્ટેક લીટકોડ સોલ્યુશન માટે જાવા પ્રોગ્રામ

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

મીન સ્ટેક લેટકોડ સોલ્યુશન માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (1): ઓ (1) તમામ કામગીરી માટે. આપણે જાણીએ છીએ કે સ્ટેક દબાણ, પ popપ અને ટોચ માટે સતત સમય લે છે. ગેટમિન માટે અમે અન્ય સ્ટેકનો ઉપયોગ કર્યો છે જે આ કાર્યને સતત સમયમાં કાર્ય કરવા માટે પણ બનાવે છે.

અવકાશ જટિલતા 

ઓ (એન): ખરાબ કિસ્સામાં, તમામ કામગીરી દબાણ હોય છે, તેથી જગ્યા જટિલતા ઓ (એન) છે.