O (1) സമയത്തിലും O (1) അധിക സ്ഥലത്തും getMin () നെ പിന്തുണയ്ക്കുന്ന ഒരു സ്റ്റാക്ക് രൂപകൽപ്പന ചെയ്യുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ഫാക്റ്റ്സെറ്റ് ഫ്ലിപ്പ്കാർട്ട് ഗോൾഡ്മാൻ സാക്സ് ഗ്രേ ഓറഞ്ച് കുലിസ മൈക്രോസോഫ്റ്റ് Paytm പബ്ലിസിസ് സാപിയന്റ് എസ്.എ.പി സ്നാപ്ഡേൽ വിഎംവെയർ
കൂനകൂട്ടുക

O (1) സമയത്തിലും O (1) അധിക സ്ഥലത്തും getMin () നെ പിന്തുണയ്ക്കുന്ന ഒരു സ്റ്റാക്ക് രൂപകൽപ്പന ചെയ്യുക. അങ്ങനെ പ്രത്യേക സ്റ്റാക്ക് ഡാറ്റാ ഘടന ഇതുപോലുള്ള സ്റ്റാക്കിന്റെ എല്ലാ പ്രവർത്തനങ്ങളെയും പിന്തുണയ്‌ക്കണം -

  • അസാധുവായ പുഷ് ()
  • int പോപ്പ് ()
  • bool isFull ()
  • bool isEmpty ()

സ്ഥിരമായ സമയത്ത്. പ്രത്യേക സ്റ്റാക്കിലെ ഏറ്റവും കുറഞ്ഞ മൂല്യം സ്ഥിരമായ സമയത്തും O (1) അധിക സ്ഥലത്തും നൽകുന്നതിന് ഒരു അധിക പ്രവർത്തനം getMin () ചേർക്കുക.

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

മിനിസ്റ്റാക്ക് നടപ്പിലാക്കുന്നതിനുള്ള ഗണിത / നിരീക്ഷിത രീതി

ഈ സമീപനത്തിൽ ഞങ്ങൾ ഏറ്റവും കുറഞ്ഞ ഘടകം ഇതായി അപ്‌ഡേറ്റുചെയ്യുന്നു -

പുഷ് () ഫംഗ്ഷനിൽ, പൂർണ്ണസംഖ്യ തള്ളേണ്ട ഏറ്റവും കുറഞ്ഞ മൂലകത്തേക്കാൾ കുറവാണെങ്കിൽ, സ്റ്റാക്കിലെ ആ സംഖ്യയുടെ മൈനസ് മിനിമം എലമെന്റിന്റെ ഇരട്ടി ഞങ്ങൾ ചേർക്കുന്നു, അത് എല്ലായ്പ്പോഴും നൽകിയ സംഖ്യയേക്കാൾ ചെറുതായിരിക്കും -

  • നൽകിയ സംഖ്യ <മിനിമം എലമെന്റ്, അതായത് നൽകിയ സംഖ്യ - മിനിമം എലമെന്റ് <0
  • // തന്നിരിക്കുന്ന സംഖ്യ ഇരുവശത്തും ചേർക്കുന്നു
  • നൽകിയ സംഖ്യ - മിനിമം എലമെന്റ് + നൽകിയ സംഖ്യ <0 + നൽകിയ പൂർണ്ണസംഖ്യ
  • 2 * നൽകിയ പൂർണ്ണസംഖ്യ - കുറഞ്ഞ ഘടകം <നൽകിയ പൂർണ്ണസംഖ്യ
  • തന്നിരിക്കുന്ന 2 * സംഖ്യ - മിനിമം എലമെന്റ് <പുതിയ മിനിമം എലമെന്റ്

അതിനാൽ ഈ ഘടകം പോപ്പ് ചെയ്യുമ്പോൾ അത് ഏറ്റവും കുറഞ്ഞ ഘടകത്തേക്കാൾ കുറവായിരിക്കും, അതിനാൽ ഞങ്ങൾ ഏറ്റവും കുറഞ്ഞ ഘടകം അപ്‌ഡേറ്റ് ചെയ്യും.

അതുപോലെ, പോപ്പ് () ഫംഗ്ഷനിൽ, നിലവിലെ ഘടകം ഏറ്റവും കുറഞ്ഞ ഘടകത്തേക്കാൾ കുറവാണെങ്കിൽ ഞങ്ങൾ അത് അപ്‌ഡേറ്റ് ചെയ്യും.

അൽഗോരിതം

  1. ഒരു ഘടന സമാരംഭിക്കുക ന്യൂസ്റ്റാക്ക് ഒരു ഫംഗ്ഷൻ സൃഷ്ടിക്കുക തള്ളുക() അതിൽ ഒരു പൂർണ്ണസംഖ്യയെ ഒരു പാരാമീറ്ററായി സ്വീകരിക്കുന്നു.
  2. സ്റ്റാക്ക് ശൂന്യമാണോയെന്ന് പരിശോധിക്കുക, സംഭരിക്കുക പൂർണ്ണസംഖ്യ ഒരു വേരിയബിൾ മിനിറ്റിൽ, പൂർണ്ണസംഖ്യ സ്റ്റാക്കിൽ ചേർത്ത് മടങ്ങുക.
  3. അല്ലെങ്കിൽ പൂർണ്ണസംഖ്യ മിനിറ്റിനേക്കാൾ കുറവാണെങ്കിൽ 2 * x - മിനിറ്റ് സ്റ്റാക്കിൽ ചേർക്കുക, മിനിറ്റ് x ആയി അപ്‌ഡേറ്റുചെയ്യുക.
  4. അല്ലെങ്കിൽ പൂർണ്ണസംഖ്യയെ സ്റ്റാക്കിലേക്ക് തള്ളുക.
  5. പോപ്പ് () എന്ന പ്രവർത്തനം സൃഷ്ടിക്കുക. സ്റ്റാക്ക് ശൂന്യമാണോയെന്ന് പരിശോധിച്ച് “സ്റ്റാക്ക് ശൂന്യമാണ്” എന്ന് മടങ്ങി മടങ്ങുക.
  6. അല്ലാത്തപക്ഷം ഘടകം സ്റ്റാക്കിന് മുകളിൽ ഒരു വേരിയബിൾ ടിയിൽ സംഭരിച്ച് മുകളിലെ ഘടകം സ്റ്റാക്കിൽ നിന്ന് നീക്കംചെയ്യുക / നീക്കംചെയ്യുക.
  7. T മിനിറ്റ് പ്രിന്റ് മിനിറ്റിനേക്കാൾ കുറവാണോയെന്ന് പരിശോധിച്ച് മിനിറ്റ് 2 * മിനിറ്റായി അപ്‌ഡേറ്റുചെയ്യുക - ടി.
  8. ടി പ്രിന്റ് ടി.
  9. GetMin () എന്ന ഫംഗ്ഷൻ സൃഷ്ടിച്ച് സ്റ്റാക്ക് ശൂന്യമാണോയെന്ന് പരിശോധിക്കുക “സ്റ്റാക്ക് ശൂന്യമാണ്”.
  10. അല്ലെങ്കിൽ ഏറ്റവും കുറഞ്ഞ ഘടകം നൽകുക.

കോഡ്

മിനിസ്റ്റാക്കിനായുള്ള സി ++ പ്രോഗ്രാം

#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

മിനിസ്റ്റാക്കിനായുള്ള ജാവ പ്രോഗ്രാം

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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (1) ഓരോ പ്രവർത്തനത്തിനും, കാരണം എല്ലാ പ്രവർത്തനങ്ങളും നിരന്തരമായ സമയത്ത് നടക്കുന്നു.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1) കാരണം ഞങ്ങൾ നിരന്തരമായ സഹായ ഇടം ഉപയോഗിക്കുന്നു. ഇൻ‌പുട്ട് സംഭരിക്കുന്നതിന് ആവശ്യമായ ഇടം അൽ‌ഗോരിത്തിന്റെ സ്പേസ് സങ്കീർ‌ണ്ണതയിലേക്ക് കണക്കാക്കില്ല.