Максимальний стек


Рівень складності Легко
Часто запитують у Apple ліфт Убер
дизайн Стек

Постановка проблеми

Проблема "Максимальний стек" говорить про розробку спеціального стека, який може виконувати такі операції:

  1. push (x): натисніть один елемент в стопку.
  2. top (): повертає елемент, який знаходиться у верхній частині стека.
  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 ()

За допомогою 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. push (x): O (1) ми можемо вкласти елементи в стек за один крок.
  2. pop (): O (1) ми можемо витягнути елемент зі стека за один крок.
  3. top (): O (1) ми можемо повернути верхній елемент стека за один крок.
  4. peekmax (): O (1) ми можемо знайти максимальний елемент у стосі за один крок.
  5. popmax (): O (n) у гіршому випадку максимальний елемент може знаходитися внизу стека.

Космічна складність

O (n) у гіршому випадку всі елементи одночасно присутні в стеку.