Mínimo stack / queue

stack = pilha, queue = fila

Neste artigo, consideraremos três problemas: primeiro, modificaremos um stack de uma forma que permita encontrar o menor elemento do stack em $O(1)$, em seguida, faremos o mesmo com a queue, e, finalmente, usaremos essas estruturas de dados para encontrar o mínimo em todas as subarrays com um tamanho fixo em uma array em $O(n)$

Stack

Queremos modificar a estrutura de dados stack de uma forma que seja possível encontrar o menor elemento no stack em tempo $O(1)$ mantendo o mesmo comportamento assintótico para adicionar e remover elementos do stack. Lembrete: em um stack apenas adicionamos e removemos elementos em uma extremidade.

Para fazer isso, não apenas armazenaremos os elementos, mas os armazenaremos em pares: o próprio elemento e o mínimo no stack, começando nesse elemento e abaixo.

stack<pair<int, int>> st;

É claro que encontrar o mínimo em todo o stack consiste apenas em verificar o valor stack.top().second.

A adição ou remoção de um novo elemento ao stack pode ser feita em tempo constante.

Implementação:

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;

Queue (método 1)

Agora queremos realizar as mesmas operações com uma queue, ou seja, queremos adicionar elementos no final e removê-los da frente.

Em uma queue, o elemento é adicionado por trás e removido pela frente, a "cabeça" é a frente.

Aqui, consideramos um método simples para modificar uma queue. Porém, ele tem uma grande desvantagem, porque a queue modificada não armazena todos os elementos.

A idéia principal é armazenar apenas os itens necessários para determinar o mínimo. Manteremos a queue em ordem não decrescente (ou seja, o menor valor será armazenado na cabeça) e, é claro, não de maneira arbitrária, o mínimo real deve estar sempre contido na queue. Dessa forma, o menor elemento sempre estará na cabeça(frente) da queue. Antes de adicionar um novo elemento à queue, basta fazer um "recorte": removeremos todos os elementos finais da fila maiores que o novo elemento e, em seguida, adicionaremos o novo elemento na queue. Dessa forma, não quebramos a ordem da queue, e também não perderemos o elemento atual se ele estiver em qualquer etapa subsequente. Todos os elementos que removemos nunca podem ser mínimos, portanto essa operação é permitida. Quando queremos extrair um elemento da cabeça, ele pode realmente não estar lá (porque o removemos anteriormente ao adicionar um elemento menor). Portanto, ao excluir um elemento de uma fila, precisamos saber o valor do elemento. Se a cabeça da queue tiver o mesmo valor, podemos removê-lo com segurança, caso contrário, não faremos nada.

Considere as implementações das operações acima:

deque<int> q;
int minimum = q.front();
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();

É claro que, em média, todas essas operações levam apenas tempo $O(1)$ (pois cada elemento pode ser puxado e removido uma única vez).

Queue (método 2)

Essa é uma modificação do método 1. Queremos poder remover elementos sem saber qual elemento precisamos remover. Podemos fazer isso armazenando o índice para cada elemento na queue. E também lembramos(contadores) quantos elementos já adicionamos e removemos.

deque<pair<int, int>> q;
int cnt_added = 0;
int cnt_removed = 0;
int minimum = q.front().first;
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++;

Queue (método 3)

Aqui consideramos outra maneira de modificar uma queue para encontrar o mínimo em $O(1)$. Essa forma é um pouco mais complicado de implementar, mas desta vez armazenamos todos os elementos. E também podemos remover um elemento da frente sem conhecer seu valor.

A idéia é reduzir o problema ao problema do stack, que já foi resolvido. Portanto, precisamos apenas aprender como simular uma queue usando dois stacks.

Criamos dois stacks, s1 e s2. É claro que esses stacks terão a forma modificada, para que possamos encontrar o mínimo em $O(1)$. Adicionaremos novos elementos ao stack s1, e removeremos elementos do stack s2. Se a qualquer momento o stack s2 estiver vazio, moveremos todos os elementos de s1 para s2 (o que essencialmente reverte a ordem desses elementos). Finalmente, encontrar o mínimo em uma queue envolve apenas encontrar o mínimo de ambos os stacks.

Assim, realizamos todas as operações (em média) em $O(1)$ (cada elemento será adicionado uma vez ao stack s1, uma vez transferido para s2, e uma vez removido de s2)

Implementação:

stack<pair<int, int>> s1, s2;
if (s1.empty() || s2.empty()) 
    minimum = s1.empty() ? s2.top().second : s1.top().second;
else
    minimum = min(s1.top().second, s2.top().second);
int minimum = s1.empty() ? new_element : min(new_element, s1.top().second);
s1.push({new_element, minimum});
if (s2.empty()) {
    while (!s1.empty()) {
        int element = s1.top().first;
        s1.pop();
        int minimum = s2.empty() ? element : min(element, s2.top().second);
        s2.push({element, minimum});
    }
}
int remove_element = s2.top().first;
s2.pop();

Encontrando o mínimo para todas as subarrays de tamanho fixo

Suponha que recebamos uma array $A$ de tamanho $N$ e um número $M \le N$. Precisamos encontrar o mínimo de cada subarray de tamanho $M$ nessa array, ou seja, precisamos encontrar: $$\min_{0 \le i \le M-1} A[i], \min_{1 \le i \le M} A[i], \min_{2 \le i \le M+1} A[i],~\dots~, \min_{N-M \le i \le N-1} A[i]$$

Temos que resolver esse problema em tempo linear, ou seja, $O(n)$.

Podemos usar qualquer uma das três queues modificadas para resolver o problema. As soluções devem ser claras: adicionamos o primeiro elemento de índice $M$ da array, encontramos e printamos seu mínimo, depois adicionamos o próximo elemento à queue e removemos o primeiro elemento da array, localizamos e printamos seu mínimo, etc. Como todas as operações com a queue são executadas em tempo constante, em média, a complexidade de todo o algoritmo será de $O(n)$.