Найдите наибольшее число в стеке, используя только операции PUSH и POP

Question

Может кто-нибудь помочь мне с Алгоритмом для этой проблемы (это вопрос интервью):

Вам дан стек.Разработайте алгоритм, чтобы найти максимальное число, используя только операции PUSH / POP.

Answer 1

Учитывая отсутствие ограничений в исходном сообщении, вы можете просто извлечь все данные и вычислить рабочий максимум:

if empty(st) -> raise exception
m <- pop(st)
while not empty(st)
    n <- pop(st)
    if n > m
        m <- n

Правка (с новым ограничением, что исходный стек неизменен иновый ресурс второго доступного стека):

if empty(st) -> raise exception
m <- pop(st)
push(alt_st, m)
while not empty(st)
    n <- pop(st)
    push(alt_st, n)
    if n > m
        m <- n
while not empty(alt_st):
    n <- pop(alt_st)
    push(st, n)

Answer 2

Поскольку исходный стек не может быть доступен только для чтения (Pop, единственный способ доступа к данным, также изменяет стек), мы должны учитывать, что ограничение «стек должен быть неизменным» означает, что мы должны восстановить его в исходное состояние после завершения.

Мы можем сделать это, используя другой стек в методе, предложенном Раймондом Хеттингером:

int get_max_from_stack(Stack stack) {
    int M = stack.pop();
    Stack aux;
    aux.push(M);
    while (!stack.empty()){
        int tmp = stack.pop();
        aux.push(tmp);
        M = max(M, tmp);
    };

    while (!aux.empty())
        stack.push(aux.pop());

    return M;
};

Answer 3

Существует два способа решения этой проблемы: либо вы можете создать функцию get_max, которая дает максимальное число в стеке, либо вы можете сохранить некоторую дополнительную информацию, используя которую вы можете указать максимальное количество в стеке O(1) операция, но за счет extra space.Я дам вам последнее решение.

Вам нужно иметь extra stack, который будет иметь максимальный элемент стека наверху, для любой конфигурации стека.

1. Всякий раз, когда вы помещаете число в свой исходный стек, выполните следующие действия для max_stack, сравните текущее значение с вершиной max_stack и вставьте на него большее значение.
2. Когда вы выдвигаетечисло просто вытолкнуть самое верхнее число из max_stack
3. Когда вам нужно узнать значение max, просто выберите вершину стека из max_stack.

Таким образом, выможно получить максимальное число за O(1) время, а операции push и pop также остаются O(1).Я мог бы дать вам код, но в этом нет ничего особенного, так как он прост.Например, если вы нажмете следующие цифры в порядке

5 - 2 - 6 - 8 - 1

max_stack будет содержать

5 - 5 - 6 - 8 - 8

и как вы pop из чисел текущий max будет наверху.

Я надеюсь, что решение ясно.