Schreiben Sie Ihre eigene Klasse, die einen Stapel implementiert, mit den Methoden push, pop und peekMax, die das maximale Element im Stapel in O(1) zurückgibt.

Ниже пример класса стека на Java с методами push, pop и peekMax, где peekMax возвращает максимальный элемент за O(1) благодаря дополнительному стеку для хранения максимумов:

import java.util.Stack;

public class MaxStack {
    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> maxStack = new Stack<>();

    public void push(int x) {
        stack.push(x);
        if (maxStack.isEmpty() || x >= maxStack.peek()) {
            maxStack.push(x);
        }
    }

    public int pop() {
        int val = stack.pop();
        if (val == maxStack.peek()) {
            maxStack.pop();
        }
        return val;
    }

    public int peekMax() {
        return maxStack.peek();
    }
}

В этом решении maxStack хранит текущие максимумы. При добавлении элемента, если он больше или равен текущему максимуму, он добавляется в maxStack. При удалении элемента, если он равен максимуму, максимум тоже удаляется. Это позволяет получить максимум за константное время.