Модификация стека и очереди для нахождения минимума за \(O (1)\)

Модификация стека

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

Для этого мы будем не только хранить элементы в стеке, но и хранить их попарно: сам элемент и минимум в стеке, начиная с этого элемента и ниже.

stack<pair<int, int>> st;

Понятно, что минимум - stack.top().second.

Реализация:

• Добавление элемента:

  int new_min = st.empty() ? new_elem : min(new_elem, st.top().second);
  st.push({new_elem, new_min});
  

• Извлечение элемента:

  int removed_element = st.top().first;
  st.pop();
  

• Нахождение минимума:

  int minimum = st.top().second;
  

Модификация очереди. Способ 1

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

Основная идея состоит в том, чтобы хранить только те элементы в очереди, которые необходимы для определения минимума.

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

• Перед добавлением нового элемента в очередь достаточно сделать разрез: мы удалим все конечные элементы очереди, которые больше, чем новый элемент, а затем добавим новый элемент в очередь. (Таким образом, мы не нарушаем порядок очереди, и мы также не потеряем текущий элемент, если он на любом последующем шаге будет минимальным. Все элементы, которые мы удалили, никогда не могут быть минимальными сами по себе, поэтому эта операция разрешена.)
• При извлечение элемент из головы, его на самом деле может не быть (потому что мы удалили его ранее, добавив меньший элемент). Поэтому при удалении элемента из очереди мы должны знать значение элемента. Если голова очереди имеет такое же значение, мы можем безопасно удалить его, иначе мы ничего не делаем.

Рассмотрим реализации вышеуказанных операций:

Реализация:

deque<int> q;

• Добавление элемента:

  while (!q.empty() && q.back() > new_element)
      q.pop_back();
  q.push_back(new_element);
  

• Извлечение элемента:

  if (!q.empty() && q.front() == remove_element)
          q.pop_front();
  

• Нахождение минимума:

  int minimum = q.front();
  

Понятно, что в среднем время выполнения всех этих операций есть \(O (1)\).

Модификация очереди. (Улучшенный 1)

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

Реализация:

deque<pair<int, int>> q;
int cnt_added = 0;
int cnt_removed = 0;

• Добавление элемента:

  while (!q.empty() && q.back().first > new_element)
          q.pop_back();
  q.push_back({new_element, cnt_added});
  cnt_added++;
  

• Извлечение элемента:

  if (!q.empty() && q.front().second == cnt_removed)
          q.pop_front();
  cnt_removed++;
  

• Нахождение минимума:

  int minimum = q.front().first;