ជង់អតិបរមា


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ផ្លែប៉ោម lyft Uber
រចនាដោយ ជង់

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

បញ្ហា“ ជង់អតិបរមា” ចែងក្នុងការរចនាជង់ពិសេសដែលអាចអនុវត្តប្រតិបត្តិការទាំងនេះបាន៖

  1. ជំរុញ (x): រុញធាតុមួយចូលក្នុងជង់។
  2. ខាងលើ ()៖ ត្រឡប់ធាតុដែលនៅខាងលើជង់។
  3. ប៉ុប ()៖ យកធាតុចេញពីជង់ដែលស្ថិតនៅខាងលើ។
  4. peekmax ()៖ ត្រឡប់ធាតុអតិបរមានៃជង់។
  5. popmax ()៖ យកធាតុអតិបរមាចេញពីជង់ហើយប្រគល់វាមកវិញ។

ប្រសិនបើជង់មានធាតុអតិបរមាច្រើនបន្ទាប់មកសម្រាប់ popmax () យកតែធាតុមួយដែលជាកំពូល។

សម្រាប់ប្រតិបត្តិការបួនចុងក្រោយនេះគឺប្រាកដថាជង់មិនទទេបើមិនដូច្នេះទេប្រតិបត្តិការទាំងនេះនឹងមិនត្រូវបានហៅទេ។

ឧទាហរណ៍

push(5);
push(1);
push(5);
top();
popMax();
top();
peekMax();
pop();
top();
5
5
1
5
1
5

ការពន្យល់

អតិបរមាជង់

វិធីសាស្រ្ត

វិធីសាស្រ្តគឺសាមញ្ញណាស់។ នៅទីនេះយើងនឹងរក្សាជង់អតិបរមាដែលនឹងតាមដានធាតុអតិបរិមានៅក្នុង ជង់ សែន​ឆ្ងាយ។ ចាប់តាំងពីការចាប់ផ្តើមប្រតិបត្តិការចំនួនបីត្រូវបានគាំទ្រដោយជង់ធម្មតាដូច្នេះយើងត្រូវរៀបចំកម្មវិធីជាពិសេសសម្រាប់ប្រតិបត្តិការពីរចុងក្រោយ។

peekmax ()

ឧបមាថាយើងមានជង់ [5,2,3,6,8] ដូច្នេះយើងនឹងរក្សាជង់មួយទៀត។ សូមដាក់ឈ្មោះវាជាជង់អតិបរិមាដែលនឹងផ្ទុកអតិបរមារហូតដល់ធាតុនោះ។ ដូច្នេះសម្រាប់ជង់ដែលបានផ្តល់ជង់អតិបរិមារបស់យើងនឹងមាន [៥.៥.៥,៦,៨] ។ តាមវិធីនេះយើងអាចរកឃើញធាតុអតិបរិមានៅក្នុងភាពស្មុគស្មាញពេលវេលាអូ (១) ។

popmax ()

ការប្រើប្រាស់ peekmax () យើងអាចរកឃើញធាតុអតិបរមានៅក្នុងជង់។ ដូច្នេះយើងនឹងបង្ហាញធាតុពីជង់ហើយរុញវាទៅជាជង់សតិបណ្ដោះអាសន្ន។ យើងនឹងធ្វើម្តងទៀតរហូតដល់យើងរកឃើញធាតុអតិបរមា។

បន្ទាប់មកយើងនឹងលេចឡើងធាតុអតិបរមាពីជង់។ បន្ទាប់ពីនោះយើងនឹងផ្ទេរធាតុទាំងអស់នៅក្នុងជង់សតិបណ្ដោះអាសន្នទៅជង់ដើមរបស់យើង។

លេខកូដ

លេខកូដ C ++ សម្រាប់ Max Stack

class MaxStack {
    public MaxStack() {
         stack<int> tmpStack, maxStack;
    }
    public void push(int x) {
        int max = maxStack.empty() ? x : maxStack.top();
        maxStack.push(max > x ? max : x);
        tmpStack.push(x);
    }
    public int pop() {
        int tmp=tmpStack.top();
        tmpStack.pop();
        maxStack.pop();
        return tmp;
    }
    public int top() {
        return tmpStack.top();
    }
    public int peekMax() {
        return maxStack.top();
    }
    public int popMax() {
        int mx = peekMax();
        stack<int> buffer;
        while (tmpStack.top() != mx){
            buffer.push(tmpStack.top());
            tmpStack.pop();
        }
        while (!buffer.empty()){
            tmpStack.push(buffer.top());
            buffer.pop();
        }
        return mx;
    }
}
push(5);
push(1);
push(5);
top();
popMax();
top();
peekMax();
pop();
top();
5
5
1
5
1
5

កូដចាវ៉ាសំរាប់អតិបរមាជេក

class MaxStack {
    Stack<Integer> tmpStack;
    Stack<Integer> maxStack;
    public MaxStack() {
        tmpStack = new Stack<Integer>();
        maxStack = new Stack<Integer>();
    }
    public void push(int x) {
        int max = maxStack.isEmpty() ? x : maxStack.peek();
        maxStack.push(max > x ? max : x);
        tmpStack.push(x);
    }
    public int pop() {
        maxStack.pop();
        return tmpStack.pop();
    }
    public int top() {
        return tmpstack.peek();
    }
    public int peekMax() {
        return maxStack.peek();
    }
    public int popMax() {
        int max = peekMax();
        Stack<Integer> buffer = new Stack<Integer>();
        while(tmpStack.top() != mx){
        	buffer.push(tmpStack.top());
        	tmpStack.pop();
        }
        while (!buffer.isEmpty()){
        	tmpStack.push(buffer.top());
        	buffer.pop();
        }
        return mx;
    }
}
push(5);
push(1);
push(5);
top();
popMax();
top();
peekMax();
pop();
top();
5
5
1
5
1
5

ការវិភាគស្មុគស្មាញ

ភាពស្មុគស្មាញពេលវេលា

  1. ជំរុញ (x): ឱ (១) យើងអាចរុញធាតុចូលទៅក្នុងជង់ជាជំហានតែមួយ។
  2. ប៉ុប ()៖ អូ (១) យើងអាចបញ្ចូលធាតុពីជង់មួយជំហាន ៗ ។
  3. ខាងលើ ()៖ ឱ (១) យើងអាចត្រឡប់ធាតុកំពូលនៃជង់ជាជំហានតែមួយ។
  4. peekmax ()៖ ឱ (១) យើងអាចរកឃើញធាតុអតិបរិមានៅក្នុងជង់ជាជំហានតែមួយ។
  5. popmax ()៖ O (n) ក្នុងករណីអាក្រក់បំផុតធាតុអតិបរិមាអាចស្ថិតនៅបាតជង់។

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

O (n) ក្នុងករណីដ៏អាក្រក់បំផុតធាតុទាំងអស់មាននៅក្នុងជង់ក្នុងពេលតែមួយ។