උපරිම තොගය


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ Apple ජංගම දුරකථන ලයිෆ්ට් Uber
නිර්මාණ අඩුක්කුව

ගැටළු ප්රකාශය

“මැක්ස් ස්ටැක්” හි ගැටලුව වන්නේ මෙම මෙහෙයුම් සිදු කළ හැකි විශේෂ තොගයක් නිර්මාණය කිරීමයි.

  1. push (x): එක් අංගයක් තොගයට තල්ලු කරන්න.
  2. ඉහළ(): තොගයේ ඉහළින් ඇති මූලද්‍රව්‍යය නැවත ලබා දෙයි.
  3. pop (): ඉහළින් ඇති තොගයෙන් මූලද්‍රව්‍යය ඉවත් කරන්න.
  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] තොගයක් ඇතැයි සිතමු, එබැවින් අපි තවත් තොගයක් පවත්වා ගනිමු. එම මූලද්‍රව්‍යය තෙක් උපරිමය ගබඩා කරන උපරිම තොගය ලෙස නම් කිරීමට ඉඩ දෙන්න. එබැවින් ලබා දී ඇති තොගය සඳහා, අපගේ උපරිම තොගය [5,5,5,6,8] වනු ඇත. මේ ආකාරයෙන්, අපට O (1) කාල සංකීර්ණයේ උපරිම මූලද්‍රව්‍යය සොයාගත හැකිය.

popmax ()

පීක්මැක්ස් () භාවිතා කිරීමෙන් අපට පහසුවෙන් තොගයේ ඇති උපරිම මූලද්‍රව්‍යය සොයාගත හැකිය. එබැවින් අපි කොටස් වලින් මූලද්‍රව්‍ය පොප් කර එය බෆර් තොගයකට තල්ලු කරමු. උපරිම මූලද්‍රව්‍යය සොයා ගන්නා තෙක් අපි මෙය නැවත කරන්නෙමු.

එවිට අපි තොගයේ උපරිම මූලද්‍රව්‍යය පොප් කරමු. ඊට පසු අපි බෆර් තොගයේ ඇති සියලුම අංග අපගේ මුල් තොගයට මාරු කරන්නෙමු.

කේතය

මැක්ස් ස්ටැක් සඳහා සී ++ කේතය

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. push (x): O (1) අපට එක පියවරකින් මූලද්‍රව්‍ය තොගයට තල්ලු කළ හැකිය.
  2. pop (): O (1) අපට එක පියවරකින් තොගයේ මූලද්‍රව්‍යයක් පොප් කළ හැකිය.
  3. ඉහළ(): O (1) අපට එක පියවරකින් තොගයේ ඉහළ අංගය ආපසු ලබා දිය හැකිය.
  4. peekmax (): O (1) අපට එක් පියවරක් තුළ තොගයේ උපරිම මූලද්‍රව්‍යය සොයාගත හැකිය.
  5. popmax (): O (n) නරකම අවස්ථාවෙහිදී උපරිම මූලද්‍රව්‍යය තොගයේ පතුලේ තිබිය හැක.

අවකාශයේ සංකීර්ණතාව

O (n) නරකම අවස්ථාවෙහිදී සියලුම මූලද්‍රව්‍යයන් එකවර තොගයේ පවතී.