Нахождение наибольшего числа в стеке

Алгоритмы прекрасны тем, что они могут решать сложные проблемы удивительно простыми способами. Однако полезность алгоритма проявляется и тогда, когда он предлагает более эффективный (или интересный) способ решения достаточно простой задачи.

Предположим, мы хотим найти наибольшее число в стеке, полностью состоящем из целых чисел. Как бы мы это сделали?

Мы должны помнить, что максимальное значение в стеке потенциально может меняться каждый раз, когда мы выталкиваем и выталкиваем из стека. Это особенно заметно в отсортированном стеке с различными значениями, где максимальное значение всегдаизменяется.

Мы не хотим переопределять максимум каждый раз, когда мы помещаем и выталкиваем в стек, если мы можем помочь. И если мы это сделаем, мы не хотим, чтобы процесс поиска был дорогостоящим.

Наивное решение

Ваш первый инстинкт поиска максимального значения в стеке, вероятно, отражен в приведенном ниже коде Ruby, который создает простой класс Stack с добавленным методом «max».

class Stack
  def initialize
    @stack = []
    @max = nil
  end
  
  def push(val) 
    @stack.push(val)
    @max = max
  end
  
  def pop
    @stack.pop
    @max = max
  end
  
  def peek(index)
    raise ArgumentError unless ([email protected]).include?(index)
    @stack[index]
  end
  def max 
    return nil if @stack.empty? 
    max = peek(0)
    @stack.length.times do |i|
      max = @stack[i] if max < @stack[i]
    end
    max
  end
  
end

Поиск максимума таким образом работает, но не слишком эффективно. Временная сложность метода «max» — это линейное время, или O(n), поскольку нам приходится просматривать весьстек каждый раз, когда мы хотим найти максимальное значение. Мы также запускаем этот алгоритм O(n) каждый раз, когда мы нажимаем и выталкиваем! Там должен быть лучший способ.

Мы должны стремиться к постоянному времени, или O(1), так как это золотой стандарт для поиска в целом. Но как нам достичь этой цели?

Умное решение

К счастью, есть алгоритм, который помогает нам быстро находить и отслеживать максимум стека по мере его создания. Этот алгоритм показан в коде Ruby ниже:

class Stack
  def initialize
    @stack = []
    @max_stack = [] # a second stack!
  end
  
  def push(val) 
    @stack.push(val)
    if @max_stack.empty? || val > peek_max
      @max_stack.push(val) 
    end
  end
  
  def pop
    last = @stack.pop
    @max_stack.pop if last == peek_max
  end
  
  def peek(index)
    raise ArgumentError unless ([email protected]).include?(index)
    @stack[index]
  end
  
  def peek_max
    @max_stack[-1]
  end
  
  def inspect 
    @stack  
  end
  def max 
    peek_max
  end
  
end

Этот алгоритм на самом деле основан на использовании двухстеков: stack и max_stack.stack отслеживают целые числа, а max_stack отслеживает максимальные значения при построении стека.

Когда мы нажимаем на stack и обнаруживаем, что переданное значение больше, чем значение, расположенное вверху max_stack, мы также нажимаем это значение на max_stack.

Когда мы извлекаем из stack и обнаруживаем, что извлеченное значение совпадает со значением, расположенным вверху max_stack, мы также извлекаем последнее значение из max_stack. Значение должно быть добавлено в оба стека вместе, поэтому они должны быть удалены вместе.

Наконец, получить максимальное значение стека — это просто посмотреть на самое верхнее значение max_stack с помощью метода peek_max. Нам удалось найти максимум за время O(1) простым поиском!

Вывод

Как и все алгоритмы, этот алгоритм «двойного стека» не идеален. Предполагается, что стек изначально пуст, что позволяет нам отслеживать максимальное значение по мере создания стека. Если стек уже инициализирован значениями и мы еще не отслеживаем максимальное значение, мы должны сделать одно из следующих действий:

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

Кроме того, при использовании алгоритма двойного стека возрастает сложность пространства, поскольку нам нужен совершенно новый стек для отслеживания максимальных значений. Вам решать, стоит ли функциональность O(1) push, pop и max lookup дополнительного необходимого пространства.

Тем не менее, как и все алгоритмы, этот, безусловно, полезно держать в наборе инструментов вашего программиста.

Предоставлено Interview Cake.