ন্যূনতম স্ট্যাক লেটকোড সমাধান


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক আপেল ব্লুমবার্গ ক্যাপিটাল ওয়ান মাইক্রোসফট আকাশবাণী
নকশা গাদা

সমস্যা বিবৃতি

নকশা ক গাদা যা ধাক্কা, পপ, শীর্ষ এবং স্থির সময়ে সর্বনিম্ন উপাদান পুনরুদ্ধারে সহায়তা করে।

পুশ (এক্স) - স্ট্যাকের উপর উপাদান এক্স চাপুন P
পপ () - স্ট্যাকের উপরে থাকা উপাদানটি সরিয়ে দেয়।
শীর্ষ () - শীর্ষ উপাদান পান।
getMin () - স্ট্যাকের সর্বনিম্ন উপাদান পুনরুদ্ধার করুন।

দ্রষ্টব্য: পদ্ধতিগুলি পপ, শীর্ষ এবং getMin ক্রিয়াকলাপ সর্বদা খালি খালি স্ট্যাকের উপর কল করা হবে।

উদাহরণ

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

ব্যাখ্যা:

মিনস্ট্যাক মিনস্ট্যাক = নতুন মিনস্ট্যাক ();
minStack.push (-2);
minStack.push (0);
minStack.push (-3);
minStack.getMin (); // রিটার্ন -৩
minStack.pop ();
মিনিস্ট্যাক.টপ (); // রিটার্ন 0
minStack.getMin (); // রিটার্ন -৩

অভিগমন

আমরা জানি একটি স্ট্যাক একটি ডেটা স্ট্রাকচার যা আমরা সহজেই শেষে একটি উপাদানকে ধাক্কা দিতে পারি এবং সহজেই সর্বশেষ sertedোকানো উপাদানটি অ্যাক্সেস বা পপ করতে পারি। এই অপারেশনগুলি স্ট (1) সময়ে স্ট্যাকের মধ্যে ঘটে। তবে এই সমস্যায় আমাদের একটি অতিরিক্ত ফাংশন গেটমিন তৈরি করতে হবে যা স্ট্যাকের সর্বনিম্ন উপাদানটিকে পুনরুদ্ধার করতে সক্ষম হবে এবং এটি ও (1) সময়েও হবে।

সুতরাং এই ডেটা স্ট্রাকচারটি ডিজাইন করার জন্য আমরা অবশ্যই স্ট্যাককে মূল ডেটা স্ট্রাকচার হিসাবে ব্যবহার করব তবে আমাদের এতে কিছুটা অতিরিক্ত অ্যালগরিদম যুক্ত করতে হবে যাতে আমরা স্থির সময়ে ন্যূনতম উপাদান পেতে সক্ষম হয়ে থাকি।

এই জন্য, একটি উদাহরণ দেখতে দিন। ধরা যাক আমাদের এই উপাদানগুলিকে স্ট্যাকের মধ্যে সন্নিবেশ করতে হবে:
5 6 4 7 5 3, এবং তারপরে পপিং শুরু করুন।

ন্যূনতম স্ট্যাক লেটকোড সমাধান

আমরা পর্যবেক্ষণ করতে পারি যে যখন আমরা উপাদানটি বর্তমান ন্যূনতমও পপ করি তখন নতুন ন্যূনতমটিকে ধাক্কা দেওয়ার আগে যেমন হয় তেমন হয়। সুতরাং আমাদের অবশ্যই পূর্ববর্তী সমস্ত ন্যূনতম উপাদানগুলির জ্ঞান থাকতে হবে যাতে হে (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

ন্যূনতম স্ট্যাক লেটকোড সমাধানের জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (1): ও (1) সমস্ত ক্রিয়াকলাপের জন্য। আমরা জানি যে স্ট্যাকটি ধাক্কা, পপ এবং শীর্ষগুলির জন্য ধ্রুবক সময় নেয়। গেটমিনের জন্য আমরা আরও একটি স্ট্যাক ব্যবহার করেছি যা এই ফাংশনটিকে ধ্রুবক সময়েও কাজ করে।

স্পেস জটিলতা ity 

চালু) : সবচেয়ে খারাপ ক্ষেত্রে সমস্ত অপারেশন ধাক্কা, সুতরাং স্থান জটিলতা হ'ল (এন)।