Monotonic Queue

The Monotonic Queue is a data structure that maintains a sequence of $n$ numbers $a_0,a_1,\dots ,a_{n-1}$ by maintaining

$$S=\{i:i\in \{0,1,\dots ,n-1\}\wedge \forall j\in \{i+1,i+2,\dots ,n-1\},a_i\ge a_j\}$$

This requires $\mathcal{O}(n)$ space.

Lemma

$$\forall i,j\in S,i<j\Rightarrow a_i\ge a_j$$

Let $\Phi =|S|$.

Push

Push updates $a_0,a_1,\dots ,a_{n-1}$ to $a_0,a_1,\dots ,a_n$ in amortized $\mathcal{O}(1)$ time and $\mathcal{O}(1)$ space.

Algorithm

Lemma

Let $S^{\prime }=\{i:i\in \{0,1,\dots ,n\}\wedge \forall j\in \{i+1,i+2,\dots ,n\},a_i\ge a_j\}$, then

$$S^{\prime }=\{i:i\in S\wedge a_i\ge a_n\}\cup \{n\}$$

Applying the lemma to find $S^{\prime }$ yields an algorithm that solves the problem in amortized $\mathcal{O}(1)$ time and $\mathcal{O}(1)$ space.

void push(int x) {
	while (!q.empty() && q.back().second < x) {
		q.pop_back();
	}
	q.emplace_back(r++, x);
}

Proof

$$\mathcal{O}(|S|-|S^{\prime }|+\Delta \Phi )=\mathcal{O}(1)$$

Pop

Pop updates $a_0,a_1,\dots ,a_{n-1}$ to $a_1,a_2,\dots ,a_{n-1}$ in amortized $\mathcal{O}(1)$ time and $\mathcal{O}(1)$ space.

Algorithm

Lemma

Let $S^{\prime }=\{i:i\in \{1,2,\dots ,n-1\}\wedge \forall j\in \{i+1,i+2,\dots ,n-1\},a_i\ge a_j\}$, then

$$S^{\prime }=S\setminus \{0\}$$

Applying the lemma to find $S^{\prime }$ yields an algorithm that solves the problem in amortized $\mathcal{O}(1)$ time and $\mathcal{O}(1)$ space.

void pop() {
	if (q.front().first == l++) {
		q.pop_front();
	}
}

Proof

$$\mathcal{O}(\Delta \Phi )=\mathcal{O}(1)$$

Top

Top finds ${\max }_{i=0}^{n-1}{a}_i$ in amortized $\mathcal{O}(1)$ time and $\mathcal{O}(1)$ space.

Algorithm

Lemma

$$\underset{i=0}{\overset{n-1}{\max }}{a}_i=a_{\min S}$$

Applying the lemma to find ${\max }_{i=0}^{n-1}{a}_i$ yields an algorithm that solves the problem in amortized $\mathcal{O}(1)$ time and $\mathcal{O}(1)$ space.

int top() {
	return q.front().second;
}

Proof

$$\mathcal{O}(\Delta \Phi )=\mathcal{O}(1)$$