Parašykite savo klasę, kuri įgyvendina staką, su metodais push, pop ir peekMax, kurie grąžina maksimalią elementą stakoje per O(1).

Ниже пример класса стека на 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. При удалении элемента, если он равен максимуму, максимум тоже удаляется. Это позволяет получить максимум за константное время.