Максимум анбора


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад себ лимф Uber
лоиҳа тӯда

Изҳороти мушкилот

Масъалаи "Max stack" мегӯяд, ки стеки махсусеро таҳия мекунад, ки ин амалҳоро иҷро карда метавонад:

  1. тела додан (х): як унсурро ба анбор тела диҳед.
  2. боло (): элементеро, ки дар болои стака ҷойгир аст, бар мегардонад.
  3. поп (): элементро аз анбора, ки дар боло аст, хориҷ кунед.
  4. peekmax (): элементи максималии стакаро бар мегардонад.
  5. popmax (): хориҷ кардани унсури максималӣ аз стек ва баргардонидани он.

Агар стек дорои якчанд унсурҳои Maximum бошад, пас барои 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]. Бо ин роҳ, мо метавонем унсури ҳадди аксарро дар мураккабии вақт (1) пайдо кунем.

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

Рамзи Java барои Max Stack

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. тела додан (х): O (1) мо метавонем дар як марҳила унсурҳоро ба анбора тела диҳем.
  2. поп (): O (1) мо метавонем унсурро аз анбора дар як марҳила барорем.
  3. боло (): O (1) мо метавонем унсури болоии стекро дар як қадам баргардонем.
  4. peekmax (): O (1) мо метавонем дар стек унсури ҳадди аксарро дар як марҳила пайдо кунем.
  5. popmax (): O (n) дар бадтарин ҳолат, унсури максималӣ метавонад дар поёни анбор бошад.

Мураккабии фазо

O (n) дар ҳолати бадтарин, дар як вақт ҳама элементҳо дар стек мавҷуданд.