最小栈

Minimum stack / Minimum queue

我们希望以这样一种方式修改堆栈数据结构，以便能够$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_back({new_elem,new_min});

// 删除元素
int removed_element = st.top().first;
st.pop();

// 查找元素
int minimum = st.top().second;

队列实现

现在我们想用队列实现相同的操作，即我们想在最后添加元素并从前面删除它们。

我们希望能够在不知道必须删除哪个元素的情况下删除元素。我们可以通过存储队列中每个元素的索引来实现这一点。我们还记得我们已经添加和删除了多少元素。

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

int minimum = q.front().first;

add elem

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

remove elem

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