ដំណោះស្រាយជែលឡេឡេកូដកូដ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ទីភ្នាក់ងារ Bloomberg សាលាមួយ ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Oracle
រចនាដោយ ជង់

សេចក្តីថ្លែងការណ៍បញ្ហា។

រចនាក ជង់ ដែលគាំទ្រការជម្រុញ, ប៉ុប, ផ្នែកខាងលើនិងទៅយកធាតុអប្បបរមានៅក្នុងពេលវេលាថេរ។

រុញ (x) - រុញធាតុ x ដាក់លើជង់។
pop () - យកធាតុចេញពីខាងលើជង់។
top () - ទទួលបានធាតុកំពូល។
getMin () - ទាញយកធាតុអប្បបរមានៅក្នុងជង់។

សម្គាល់ៈវិធីសាស្រ្ត pop, top និង getMin ប្រតិបត្តិការតែងតែត្រូវបានគេហៅថាជង់មិនទទេ។

ឧទាហរណ៍

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

ការពន្យល់:

MinStack minStack = មីនីស្ទេកថ្មី ();
minStack.push (-២);
minStack.push (០);
minStack.push (-២);
minStack.getMin (); // ត្រឡប់ -៣
minStack.pop ();
minStack.top (); // ត្រឡប់ ០
minStack.getMin (); // ត្រឡប់ -៣

វិធីសាស្រ្ត

យើងដឹងថាជង់គឺជារចនាសម្ព័ន្ធទិន្នន័យដែលយើងអាចរុញធាតុមួយនៅចុងបញ្ចប់បានយ៉ាងងាយស្រួលហើយក៏អាចចូលរឺចូលធាតុដែលបានបញ្ចូលចុងក្រោយបានយ៉ាងងាយស្រួល។ ប្រតិបត្ដិការទាំងនេះកើតឡើងនៅក្នុងពេលវេលាអូ (1) ក្នុងជង់។ ប៉ុន្តែនៅក្នុងបញ្ហានេះយើងត្រូវធ្វើមុខងារបន្ថែម getMin ដែលគួរតែអាចទាញយកធាតុអប្បបរមានៅក្នុងជង់ហើយនោះក៏មាននៅក្នុងអូ (1) ផងដែរ។

ដូច្នេះដើម្បីរៀបចំរចនាសម្ព័នទិន្នន័យនេះយើងនឹងប្រើជង់ជារចនាសម្ព័ន្ធទិន្នន័យសំខាន់ប៉ុន្តែយើងត្រូវបន្ថែមក្បួនដោះស្រាយបន្ថែមមួយចំនួនដើម្បីឱ្យយើងអាចទទួលបានធាតុអប្បបរមាក្នុងពេលវេលាថេរ។

ចំពោះបញ្ហានេះសូមមើលឧទាហរណ៍។ ឧបមាថាយើងត្រូវបញ្ចូលធាតុទាំងនេះជាជង់តាមលំដាប់លំដោយ៖
៥ ៦ ៤ ៧ ៥ ៣ ហើយបន្ទាប់មកចាប់ផ្តើមលោត។

ដំណោះស្រាយជែលឡេឡេកូដកូដ

យើងអាចសង្កេតឃើញថានៅពេលដែលយើងចាប់ធាតុដែលជាអប្បបរមាបច្ចុប្បន្ននោះអប្បបរមាថ្មីគឺដូចគ្នានឹងមុនពេលរុញវាដែរ។ ដូច្នេះយើងត្រូវតែមានចំណេះដឹងអំពីធាតុអប្បបរមាមុន ៗ រហូតមកដល់ពេលនេះដូច្នេះយើងអាចទាញយកអប្បបរមាបន្ទាប់ពីការដកធាតុអប្បបរមាបច្ចុប្បន្នចេញនៅក្នុងពេលវេលាអូ (១) ។

សម្រាប់នេះយើងអាចប្រើជង់មួយទៀតដែលនឹងផ្ទុកតែធាតុអប្បបរមា (តំណាងដោយពណ៌បៃតងនៅក្នុងរូបភព) នៃជង់សំខាន់។ ដូច្នេះធាតុកំពូលនៃជង់អប្បបរមានឹងប្រាប់ធាតុអប្បបរមាបច្ចុប្បន្ន។

កំឡុងពេលបញ្ចូលរឺដកធាតុយើងនឹងធ្វើបច្ចុប្បន្នភាពជង់មីនដូចខាងក្រោម៖

  • ប្រសិនបើធាតុដែលបានរុញថ្មីតិចជាងឬស្មើនឹងអប្បបរមាបច្ចុប្បន្ននោះយើងរុញធាតុនេះទៅជាជង់អប្បបរមាដើម្បីធ្វើបច្ចុប្បន្នភាពអប្បបរមាបច្ចុប្បន្ន។
  • ប្រសិនបើធាតុដែលបានបង្កើតឡើងមានចំនួនស្មើនឹងអប្បបរមាបច្ចុប្បន្នបន្ទាប់មកយើងយកធាតុនេះចេញពីជង់អប្បបរមាដើម្បីធ្វើបច្ចុប្បន្នភាពអប្បបរមាបច្ចុប្បន្ន។

ការអនុវត្តន៍

កម្មវិធី C ++ សំរាប់ដំណោះស្រាយជែនឡេសឡេបកូដ

#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) សម្រាប់ប្រតិបត្តិការទាំងអស់។ ដូចដែលយើងដឹងជង់ចំណាយពេលថេរសម្រាប់ការរុញប៉ុបនិងកំពូល។ សម្រាប់ getMin យើងបានប្រើជង់មួយទៀតដែលធ្វើឱ្យមុខងារនេះដំណើរការក្នុងពេលវេលាថេរ។

ភាពស្មុគស្មាញនៃលំហ 

O (n)៖ ក្នុងករណីអាក្រក់បំផុតប្រតិបត្តិការទាំងអស់ត្រូវបានជំរុញដូច្នេះភាពស្មុគស្មាញនៃលំហគឺ O (n) ។