You have an empty sequence, and you will be given N queries. Each query is one of these three types: 1 x -Push the element x into the stack. 2 -Delete the element present at the top of the stack. 3 -Print the maximum element in the stack. the getMax

Добавлена: 16.05.2026
Обновлена: 16.05.2026
Предмет: Программирование
Автор: Кэмп

#Основы алгоритмизации и программирования
#Структуры и алгоритмы обработки данных

Условие:

You have an empty sequence, and you will be given N queries. Each query is one of these three types:

1 x -Push the element x into the stack.
2 -Delete the element present at the top of the stack.
3 -Print the maximum element in the stack.
\nComplete the getMax function in the editor below.
\ngetMax has the following parameters:
- string operations[n]: operations as strings
\nReturns: - int[]: the answers to each type 3 query
\nInput Format: The first line of input contains an integer, n. The next n lines each contain an above mentioned query.
\nConstraints: 1<=n<=10^5; 1<=x<=10^9; 1<=type<=3. All queries are valid.

Решение:

Здравствуйте! Я готов помочь вам разобраться с задачей "Maximum Element". Это классическая задача на реализацию стека, где требуется эффективно находить максимальный элемент среди всех хранящихся в стеке.

Поскольку нам нужно выполнять операции добавления (push), удаления (pop) и поиска максимума (get max) за эффективное время (в идеале $O(1)$ для всех операций), использование стандартного стека не подойдет, так как поиск максимума в нем займет $O(N)$ времени, где $N$ — количество элементов в стеке.

Для достижения $O(1)$ времени для всех операций мы будем использовать два стека:

Основной стек (mainStack): Хранит все элементы в порядке их добавления, как обычный стек.
Стек максимумов (maxStack): Хранит максимальные элементы, которые *...