കുറഞ്ഞ സ്റ്റാക്ക് ലീറ്റ്കോഡ് പരിഹാരം


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

പ്രശ്നം പ്രസ്താവന

രൂപകൽപ്പന a സ്റ്റാക്ക് അത് പുഷ്, പോപ്പ്, ടോപ്പ്, സ്ഥിരമായ സമയത്ത് ഏറ്റവും കുറഞ്ഞ ഘടകം വീണ്ടെടുക്കൽ എന്നിവയെ പിന്തുണയ്ക്കുന്നു.

പുഷ് (x) - ഘടകം x സ്റ്റാക്കിലേക്ക് പുഷ് ചെയ്യുക.
പോപ്പ് () - സ്റ്റാക്കിന് മുകളിലുള്ള ഘടകം നീക്കംചെയ്യുന്നു.
മുകളിൽ () - മുകളിലെ ഘടകം നേടുക.
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) സമയത്താണ് സംഭവിക്കുന്നത്. എന്നാൽ ഈ പ്രശ്‌നത്തിൽ‌ ഞങ്ങൾ‌ ഒരു അധിക പ്രവർ‌ത്തനം നേടേണ്ടതുണ്ട്, അത് സ്റ്റാക്കിലെ ഏറ്റവും കുറഞ്ഞ ഘടകം വീണ്ടെടുക്കാൻ‌ കഴിയും, കൂടാതെ O (1) സമയത്തിലും.

അതിനാൽ ഈ ഡാറ്റാ ഘടന രൂപകൽപ്പന ചെയ്യുന്നതിന് ഞങ്ങൾ പ്രധാന ഡാറ്റാ ഘടനയായി സ്റ്റാക്ക് ഉപയോഗിക്കും, പക്ഷേ അതിൽ കുറച്ച് അധിക അൽഗോരിതം ചേർക്കേണ്ടതിനാൽ സ്ഥിരമായ സമയത്ത് കുറഞ്ഞ ഘടകം നേടാൻ ഞങ്ങൾക്ക് കഴിയും.

ഇതിനായി, ഒരു ഉദാഹരണം കാണാം. ക്രമത്തിൽ ഈ ഘടകങ്ങൾ സ്റ്റാക്കിൽ ചേർക്കണമെന്ന് കരുതുക:
5 6 4 7 5 3, തുടർന്ന് പോപ്പിംഗ് ആരംഭിക്കുക.

കുറഞ്ഞ സ്റ്റാക്ക് ലീറ്റ്കോഡ് പരിഹാരം

നിലവിലെ മിനിമം ആയ മൂലകം പോപ്പ് ചെയ്യുമ്പോൾ പുതിയ മിനിമം തള്ളുന്നതിനുമുമ്പ് അത് സമാനമാണെന്ന് നമുക്ക് നിരീക്ഷിക്കാനാകും. അതിനാൽ മുമ്പത്തെ എല്ലാ മിനിമം ഘടകങ്ങളെപ്പറ്റിയുമുള്ള അറിവ് നമുക്കുണ്ടായിരിക്കണം, അതിലൂടെ O (1) സമയത്തിലെ നിലവിലെ ഏറ്റവും കുറഞ്ഞ മൂലകം നീക്കം ചെയ്തതിനുശേഷം ഏറ്റവും കുറഞ്ഞത് വീണ്ടെടുക്കാൻ കഴിയും.

ഇതിനായി നമുക്ക് മറ്റൊരു സ്റ്റാക്ക് ഉപയോഗിക്കാം, അത് പ്രധാന സ്റ്റാക്കിന്റെ ഏറ്റവും കുറഞ്ഞ ഘടകം (അത്തിയിൽ പച്ച നിറത്തിൽ പ്രതിനിധീകരിക്കുന്നു) മാത്രം സംഭരിക്കും. അതിനാൽ മിനിമം സ്റ്റാക്കിന്റെ മുകളിലെ ഘടകം നിലവിലെ മിനിമം ഘടകത്തെ അറിയിക്കും.

ഒരു ഘടകം ചേർക്കുമ്പോഴോ നീക്കംചെയ്യുമ്പോഴോ ഞങ്ങൾ മിൻ സ്റ്റാക്ക് ചുവടെ അപ്‌ഡേറ്റ് ചെയ്യും:

  • പുതിയ പുഷ് ചെയ്ത ഘടകം നിലവിലെ മിനിമത്തേക്കാൾ കുറവോ തുല്യമോ ആണെങ്കിൽ, നിലവിലെ മിനിമം അപ്‌ഡേറ്റ് ചെയ്യുന്നതിന് ഞങ്ങൾ ഈ ഘടകത്തെ മിനിറ്റ് സ്റ്റാക്കിലേക്ക് തള്ളുന്നു.
  • പോപ്പ് ചെയ്ത ഘടകം നിലവിലെ മിനിമത്തിന് തുല്യമാണെങ്കിൽ, നിലവിലെ മിനിമം അപ്‌ഡേറ്റ് ചെയ്യുന്നതിന് ഞങ്ങൾ ഈ ഘടകം മിനിറ്റ് സ്റ്റാക്കിൽ നിന്നും നീക്കംചെയ്യുന്നു.

നടപ്പിലാക്കൽ

മിൻ സ്റ്റാക്ക് ലീറ്റ്കോഡ് പരിഹാരത്തിനായുള്ള സി ++ പ്രോഗ്രാം

#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

മിൻ സ്റ്റാക്ക് ലീറ്റ്കോഡ് പരിഹാരത്തിനായുള്ള സങ്കീർണ്ണത വിശകലനം

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

O (1): എല്ലാ പ്രവർത്തനങ്ങൾക്കും O (1). പുഷ്, പോപ്പ്, ടോപ്പ് എന്നിവയ്‌ക്ക് സ്റ്റാക്ക് സ്ഥിരമായ സമയമെടുക്കുമെന്ന് നമുക്കറിയാം. GetMin നായി ഞങ്ങൾ മറ്റൊരു സ്റ്റാക്ക് ഉപയോഗിച്ചു, ഇത് സ്ഥിരമായ സമയത്ത് പ്രവർത്തിക്കാൻ ഈ ഫംഗ്ഷനെ സഹായിക്കുന്നു.

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

O (n): ഏറ്റവും മോശം അവസ്ഥയിൽ എല്ലാ പ്രവർത്തനങ്ങളും പുഷ് ആണ്, അതിനാൽ സ്ഥല സങ്കീർണ്ണത O (n) ആണ്.