O (1) સમય અને O (1) વધારાની જગ્યામાં getMin () ને સપોર્ટ કરતું સ્ટેક ડિઝાઇન કરો


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

O (1) સમય અને O (1) વધારાની જગ્યામાં getMin () ને સપોર્ટ કરતું સ્ટેક ડિઝાઇન કરો. આમ ખાસ સ્ટેક ડેટા સ્ટ્રક્ચરે સ્ટેકની બધી કામગીરીને ટેકો આપવો જ જોઇએ -

  • રદબાતલ દબાણ ()
  • પૂર્ણાંક પ popપ ()
  • બુલ સંપૂર્ણ છે ()
  • બુલ ઇફેટી છે ()

સતત સમય માં. સતત સમય અને ઓ (1) વધારાની જગ્યામાં વિશેષ સ્ટેકમાં ન્યૂનતમ મૂલ્ય પરત કરવા માટે વધારાના getપરેશન ગેટમિન () ઉમેરો.

O (1) સમય અને O (1) વધારાની જગ્યામાં getMin () ને સપોર્ટ કરતું સ્ટેક ડિઝાઇન કરો

ઉદાહરણ

push(30)
push(20)
push(10)
getMin()
pop()
getMin()
Minimum element : 10
Popped element : 10
Minimum element : 20
push(500)
push(50)
push(5)
getMin()
pop()
getMin()
Minimum element : 5
Popped element : 5
Minimum element : 50

મિનસ્ટackકના અમલ માટેની ગણિત / અવલોકન પદ્ધતિ

આ અભિગમમાં આપણે લઘુત્તમ તત્વને આ પ્રમાણે અપડેટ કરી રહ્યાં છીએ -

પુશ () ફંક્શનમાં જો પૂર્ણાંકને દબાણ કરવું તે ન્યૂનતમ તત્વ કરતા ઓછું હોય છે જે આપણે સ્ટેકમાં પૂર્ણાંક માઇનસ લઘુત્તમ તત્વ કરતાં બે વાર દાખલ કરી રહ્યા છીએ જે આપેલ પૂર્ણાંક કરતા હંમેશાં નાનું રહેશે -

  • આપેલ પૂર્ણાંક <લઘુત્તમ તત્વ જેનો અર્થ છે પૂર્ણાંક - ન્યૂનતમ તત્વ <0
  • // બંને બાજુએ આપેલ પૂર્ણાંક ઉમેરવું
  • આપેલ પૂર્ણાંક - ન્યૂનતમ તત્વ + આપેલ પૂર્ણાંક <0 + આપેલ પૂર્ણાંક
  • 2 * આપેલ પૂર્ણાંક - ન્યૂનતમ તત્વ <પૂર્ણાંક
  • આપણે 2 * આપેલ પૂર્ણાંક - લઘુત્તમ તત્વ <ન્યુનત્તમ તત્વ "સમાપ્ત કરી શકીએ છીએ

તેથી જ્યારે આ તત્વને બહાર કા .તા તે લઘુત્તમ તત્વ કરતા ઓછું હશે તેથી અમે ન્યૂનતમ તત્વને અપડેટ કરીશું.

એ જ રીતે, પ popપ () ફંક્શનમાં, જો વર્તમાન તત્વ ન્યૂનતમ તત્વ કરતા ઓછું હોય તો અમે તેને અપડેટ કરીશું.

અલ્ગોરિધમ

  1. સ્ટ્રક્ચર શરૂ કરો newStack અને ફંકશન બનાવો દબાણ() તેમાં જે એક પરિમાણ તરીકે પૂર્ણાંક સ્વીકારે છે.
  2. સ્ટેક ખાલી છે કે નહીં તે તપાસો, સ્ટોર કરો પૂર્ણાંક ચલ મિનિટમાં, સ્ટેક અને વળતરમાં પૂર્ણાંક દાખલ કરો.
  3. બાકી જો પૂર્ણાંક મિનિટ કરતા ઓછો હોય તો 2 * x - મિનિટ સ્ટેક અને મિનિટને x તરીકે અપડેટ કરો.
  4. બાકી સ્ટેક માં પૂર્ણાંક દબાણ.
  5. ફંક્શન પ popપ () બનાવો. સ્ટેક ખાલી પ્રિન્ટ છે કે કેમ તે તપાસો “સ્ટેક ખાલી છે” અને પાછા ફરો.
  6. અન્યથા ચલ ટીમાં તત્વને સ્ટેકની ટોચ પર સ્ટોર કરો અને સ્ટેકમાંથી ટોચનાં તત્વને પ popપ કરો / દૂર કરો.
  7. જો ટી પ્રિન્ટ મિનિટ કરતાં ઓછું છે કે નહીં તે તપાસો અને મિનિટને 2 * મિનિટ - ટી તરીકે અપડેટ કરો.
  8. બાકી પ્રિન્ટ ટી.
  9. GetMin () ફંક્શન બનાવો અને સ્ટેક ખાલી પ્રિન્ટ છે કે નહીં તેની તપાસ કરો "સ્ટેક ખાલી છે".
  10. બાકી ન્યુનત્તમ તત્વ પાછા.

કોડ

મિનસ્ટ minક માટે સી ++ પ્રોગ્રામ

#include <bits/stdc++.h> 
using namespace std; 
  
struct newStack{ 
    stack<int> s; 
    int min; 
  
    void getMin(){ 
        if(s.empty()){ 
            cout<<"Stack is empty\n"; 
        }
        else{
            cout<<"Minimum element : "<<min<<"\n"; 
        }    
    } 
  
    void pop(){ 
        if(s.empty()){ 
            cout<<"Stack is empty\n"; 
            return; 
        } 
  
        cout<<"Popped element : "; 
        int t = s.top(); 
        s.pop(); 
  
        if(t<min){ 
            cout<<min<< "\n"; 
            min = 2*min - t; 
        } 
  
        else{
            cout<<t<< "\n";
        }    
    } 
  
    void push(int x){ 
        if(s.empty()){ 
            min = x; 
            s.push(x); 
            return; 
        } 
  
        if(x < min){ 
            s.push(2*x - min); 
            min = x; 
        } 
  
        else{
           s.push(x);
        }   
    } 
}; 
 
int main(){
    newStack s; 
    
    s.push(30);
    s.push(20);
    s.push(10);
    s.getMin();
    s.pop();
    s.getMin();
  
    return 0; 
}
Minimum element : 10
Popped element : 10
Minimum element : 20

મિનસ્ટackક માટે જાવા પ્રોગ્રામ

import java.util.*; 
  
class newStack{ 
    Stack<Integer> s; 
    Integer min; 
  
    newStack(){ 
        s = new Stack<Integer>(); 
    } 
  
    void getMin(){ 
        if(s.isEmpty()) 
            System.out.println("Stack is empty"); 
  
        else{
            System.out.println("Minimum element : " + min);
        }    
    } 
  
    void pop(){ 
        if (s.isEmpty()){ 
            System.out.println("Stack is empty"); 
            return; 
        } 
  
        System.out.print("Popped element : "); 
        Integer t = s.pop(); 
  
        if(t<min){ 
            System.out.println(min); 
            min = 2*min - t; 
        } 
  
        else{
            System.out.println(t);
        }    
    } 
  
    void push(Integer x){ 
        if(s.isEmpty()){ 
            min = x; 
            s.push(x); 
            return; 
        } 
  
        if(x<min){ 
            s.push(2*x - min); 
            min = x; 
        } 
  
        else{
            s.push(x); 
        }    
    } 
}; 
  
public class Main{ 
    public static void main(String[] args){ 
        newStack s = new newStack(); 
        
        s.push(30);
        s.push(20);
        s.push(10);
        s.getMin();
        s.pop();
        s.getMin();
        
    } 
}
Minimum element : 10
Popped element : 10
Minimum element : 20

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (1) દરેક forપરેશન માટે, કારણ કે તમામ કામગીરી સતત સમય માં કરવામાં આવી રહી છે.

અવકાશ જટિલતા

ઓ (1) કારણ કે આપણે દૂષિત સહાયક જગ્યા વાપરી રહ્યા છીએ. ઇનપુટ સ્ટોર કરવા માટે જરૂરી જગ્યા એલ્ગોરિધમની જગ્યાની જટિલતા તરફ ગણતરી કરતી નથી.