Here I will describe a way to maintain deque that will allow us to find the smallest element in deque at any time. Maybe this technique is well-known, but I couldn’t find any info about it, so decided to post it there.↵
↵
### Minimum Stack and Minimum Queue↵
↵
First, we want to maintain stack with the ability to find its smallest element whenever we want. Let's store minimums on the corresponding prefix of stack along with elements. This way we can easily push/pop elements and find minimum in $O(1)$.↵
↵
Minimum Queue can be maintained using two Minimum Stacks: one stack will store some elements from beginning, and the other from the end. We will push elements to the second stack and pop them from the first. If the first stack becomes empty, then we move all elements from the second stack into the first. It will work in $O(N)$ amortized.↵
↵
### Minimum Deque↵
↵
Actually, we can maintain Minimum Deque the same way we maintain Minimum Queue, but it will be too slow. The problem is the number of moved elements: in the worst case we will move all elements every operation by removing first and last element alternately. So instead of moving all elements let's move only a half of them at a time. Turns out it works in $O(N)$!↵
↵
But how to prove it? Let $k_i$ be the number of elements deque contained right before $i_{th}$ operation of moving elements between stacks, the algorithm above obviously works in $O(N + \sum k_i)$. Also $k_i = \frac{k_{i-1}}{2} + q_i$, where $q_i$ is the number of elements added between operations $i-1$ and $i$. We can see that $q_i$ contributes $q_i$ to $k_i$, $\frac{q_i}{2}$ to $k_{i+1}$, $\frac{q_i}{4}$ to $k_{i+2}$ and so on. It follows that $q_i$ contributes $O(q_i)$ to $O(\sum k_i)$. $\sum q_i$ is obviously $\leq N$, so $O(\sum k_i) = O(N)$. That's why the algorithm above is $O(N)$ amortized.↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
struct minstack {↵
stack<pair<int, int>> st;↵
int getmin() {return st.top().second;}↵
bool empty() {return st.empty();}↵
int size() {return st.size();}↵
void push(int x) {↵
int mn = x;↵
if (!empty()) mn = min(mn, getmin());↵
st.push({x, mn});↵
}↵
void pop() {st.pop();}↵
int top() {return st.top().first;}↵
void swap(minstack &x) {st.swap(x.st);}↵
};↵
↵
struct mindeque {↵
minstack l, r, t;↵
void rebalance() {↵
bool f = false;↵
if (r.empty()) {f = true; l.swap(r);}↵
int sz = r.size() / 2;↵
while (sz--) {t.push(r.top()); r.pop();}↵
while (!r.empty()) {l.push(r.top()); r.pop();}↵
while (!t.empty()) {r.push(t.top()); t.pop();}↵
if (f) l.swap(r);↵
}↵
int getmin() {↵
if (l.empty()) return r.getmin();↵
if (r.empty()) return l.getmin();↵
return min(l.getmin(), r.getmin());↵
}↵
bool empty() {return l.empty() && r.empty();}↵
int size() {return l.size() + r.size();}↵
void push_front(int x) {l.push(x);}↵
void push_back(int x) {r.push(x);}↵
void pop_front() {if (l.empty()) rebalance(); l.pop();}↵
void pop_back() {if (r.empty()) rebalance(); r.pop();}↵
int front() {if (l.empty()) rebalance(); return l.top();}↵
int back() {if (r.empty()) rebalance(); return r.top();}↵
void swap(mindeque &x) {l.swap(x.l); r.swap(x.r);}↵
};↵
~~~~~↵
</spoiler>↵
↵
↵
### Minimum Stack and Minimum Queue↵
↵
First, we want to maintain stack with the ability to find its smallest element whenever we want. Let's store minimums on the corresponding prefix of stack along with elements. This way we can easily push/pop elements and find minimum in $O(1)$.↵
↵
Minimum Queue can be maintained using two Minimum Stacks: one stack will store some elements from beginning, and the other from the end. We will push elements to the second stack and pop them from the first. If the first stack becomes empty, then we move all elements from the second stack into the first. It will work in $O(N)$ amortized.↵
↵
### Minimum Deque↵
↵
Actually, we can maintain Minimum Deque the same way we maintain Minimum Queue, but it will be too slow. The problem is the number of moved elements: in the worst case we will move all elements every operation by removing first and last element alternately. So instead of moving all elements let's move only a half of them at a time. Turns out it works in $O(N)$!↵
↵
But how to prove it? Let $k_i$ be the number of elements deque contained right before $i_{th}$ operation of moving elements between stacks, the algorithm above obviously works in $O(N + \sum k_i)$. Also $k_i = \frac{k_{i-1}}{2} + q_i$, where $q_i$ is the number of elements added between operations $i-1$ and $i$. We can see that $q_i$ contributes $q_i$ to $k_i$, $\frac{q_i}{2}$ to $k_{i+1}$, $\frac{q_i}{4}$ to $k_{i+2}$ and so on. It follows that $q_i$ contributes $O(q_i)$ to $O(\sum k_i)$. $\sum q_i$ is obviously $\leq N$, so $O(\sum k_i) = O(N)$. That's why the algorithm above is $O(N)$ amortized.↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
struct minstack {↵
stack<pair<int, int>> st;↵
int getmin() {return st.top().second;}↵
bool empty() {return st.empty();}↵
int size() {return st.size();}↵
void push(int x) {↵
int mn = x;↵
if (!empty()) mn = min(mn, getmin());↵
st.push({x, mn});↵
}↵
void pop() {st.pop();}↵
int top() {return st.top().first;}↵
void swap(minstack &x) {st.swap(x.st);}↵
};↵
↵
struct mindeque {↵
minstack l, r, t;↵
void rebalance() {↵
bool f = false;↵
if (r.empty()) {f = true; l.swap(r);}↵
int sz = r.size() / 2;↵
while (sz--) {t.push(r.top()); r.pop();}↵
while (!r.empty()) {l.push(r.top()); r.pop();}↵
while (!t.empty()) {r.push(t.top()); t.pop();}↵
if (f) l.swap(r);↵
}↵
int getmin() {↵
if (l.empty()) return r.getmin();↵
if (r.empty()) return l.getmin();↵
return min(l.getmin(), r.getmin());↵
}↵
bool empty() {return l.empty() && r.empty();}↵
int size() {return l.size() + r.size();}↵
void push_front(int x) {l.push(x);}↵
void push_back(int x) {r.push(x);}↵
void pop_front() {if (l.empty()) rebalance(); l.pop();}↵
void pop_back() {if (r.empty()) rebalance(); r.pop();}↵
int front() {if (l.empty()) rebalance(); return l.top();}↵
int back() {if (r.empty()) rebalance(); return r.top();}↵
void swap(mindeque &x) {l.swap(x.l); r.swap(x.r);}↵
};↵
~~~~~↵
</spoiler>↵
↵
