Найдите наибольшее число в стеке, используя только 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 

Edit (с новым ограничением, что первоначальный стек без изменений и новый ресурс второго доступного стека):

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, единственный способ получить доступ к данным, а также модифицирует стек), мы должны учитывать, что «й e сток должен быть неизменным "ограничение означает, что мы должны восстановить его в исходное состояние после того, как мы закончим.

Мы можем сделать это с помощью другого стека в методе, предложенном Raymond Хеттингер:

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) времени и нажимные и поп-операции также остаются O(1). Я мог бы дать вам код, но в нем нет ничего особенного, поскольку он прямолинейный. Например, если вы нажимаете следующие номера в порядке

5 - 2 - 6 - 8 - 1

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

5 - 5 - 6 - 8 - 8

и как вы pop чисел тока max будет на самом верху.

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