Neste artigo, exploraremos duas questões algorítmicas comuns que se beneficiam do uso inteligente de estruturas de dados: encontrar o valor máximo em uma janela deslizante e determinar os K elementos com maior frequência em um array. Ambas as soluções demonstram a eficácia de estruturas como deque e heap para otimizar o desempenho.

Problema: Máximo da Janela Deslizante (LeetCode 239)

Considere um array de inteiros numeros e um tamanho de janela k. Uma janela deslizante de tamanho k percorre o array da esquerda para a direita, movendo-se uma posição por vez. Nosso objetivo é retornar um array contendo o valor máximo de cada janela.

Exemplo Ilustrativo:

Entrada: numeros = [1,3,-1,-3,5,3,6,7], k = 3
Saída:   [3,3,5,5,6,7]

Explicação da movimentação da janela:
Janela             Máximo
---------------    -----
[1  3  -1] -3  5  3  6  7    3
 1 [3  -1  -3] 5  3  6  7    3
 1  3 [-1  -3  5] 3  6  7    5
 1  3  -1 [-3  5  3] 6  7    5
 1  3  -1  -3 [5  3  6] 7    6
 1  3  -1  -3  5 [3  6  7]   7

Abordagem com Deque Monotônica

A chave para resolver este problema eficientemente é utilizar uma fila de duas extremidades (deque) para manter os elementos da janela em ordem decrescente. Esta deque será "monotônica", garantindo que o elemento na frente (front) seja sempre o maior valor na janela atual.

A deque armazenará os índices dos elementos do array, em vez dos próprioss valores. Isso nos permite verificar facilmente se um elemento saiu da janela e lidar com valores duplicados de forma robusta.

• Ao adicionar um novo elemento (com índice i):
  • Remova os índices do final (back) da deque cujos valores correspondetnes em numeros são menores ou iguais ao valor de numeros[i]. Isso garante que a deque mantenha a propriedade decrescente e que elementos menores que um novo elemento à direita nunca serão máximos.
  • Adicione o índice i ao final da deque.
• Ao remover um elemento (quando a janela desliza e o elemento mais antigo, com índice i - k, sai):
  • Verifique se o índice na frente da deque está fora dos limites da janela atual (ou seja, é menor ou igual a i - k). Se sim, remova-o da frente.
• Após cada operação de deslizamento da janela, o valor correspondente ao índice na frente da deque (numeros[filaDecrescente.front()]) será o máximo da janela atual.

Implementação em C++:

// Complexidade de tempo: O(N)
// Complexidade de espaço: O(K)
#include <vector>
#include <deque>
#include <algorithm> // Para std::max, embora não usado diretamente na deque

class SolucaoJanelaDeslizante {
public:
    std::vector<int> encontrarMaximosJanela(const std::vector<int>& dados, int tamanhoJanela) {
        std::vector<int> resultadosMax;
        std::deque<int> filaIndicesDecrescente; // Armazena índices, mantendo dados[índice] em ordem decrescente

        // Processa a primeira janela (índices de 0 a tamanhoJanela - 1)
        for (int i = 0; i < tamanhoJanela; ++i) {
            // Remove índices do final que apontam para valores menores ou iguais ao dado atual
            while (!filaIndicesDecrescente.empty() && dados[i] >= dados[filaIndicesDecrescente.back()]) {
                filaIndicesDecrescente.pop_back();
            }
            filaIndicesDecrescente.push_back(i); // Adiciona o índice atual
        }
        // O máximo da primeira janela é o valor no índice na frente da deque
        resultadosMax.push_back(dados[filaIndicesDecrescente.front()]);

        // Processa as janelas subsequentes
        for (int i = tamanhoJanela; i < dados.size(); ++i) {
            // Remove o índice da frente se ele estiver fora da janela atual
            if (!filaIndicesDecrescente.empty() && filaIndicesDecrescente.front() <= (i - tamanhoJanela)) {
                filaIndicesDecrescente.pop_front();
            }

            // Remove índices do final que apontam para valores menores ou iguais ao dado atual
            while (!filaIndicesDecrescente.empty() && dados[i] >= dados[filaIndicesDecrescente.back()]) {
                filaIndicesDecrescente.pop_back();
            }
            filaIndicesDecrescente.push_back(i); // Adiciona o índice atual

            // O máximo da janela atual é o valor no índice na frente da deque
            resultadosMax.push_back(dados[filaIndicesDecrescente.front()]);
        }
        return resultadosMax;
    }
};

Problema: K Elementos Mais Frequentes (LeetCode 347)

Dada uma lista de inteiros numeros e um valor inteiro k, devemos retornar os k elementos que aparecem com maior frequência. A ordem dos elementos na saída não importa.

Exemplo Ilustrativo:

Entrada: numeros = [1,1,1,2,2,3], k = 2
Saída:   [1,2]

Explicação: '1' aparece 3 vezes, '2' aparece 2 vezes, '3' aparece 1 vez.
Os 2 elementos mais frequentes são 1 e 2.

Requisito de Desempenho:

A complexidade de tempo do algoritmo deve ser superior a O(N log N), onde N é o tamanho do array.

Abordagem com Mapa de Frequência e Heap de Mínimos

Para resolver este problema de forma eficiente, seguiremos dois passos principais:

1. Contagem de Frequência: Primeiramente, utilizamos um mapa hash (std::unordered_map em C++) para contar a frequência de cada número no array.
2. Seleção com Heap de Mínimos: Em seguida, empregamos uma fila de prioridade (std::priority_queue) configurada como um heap de mínimos. Esta estrutura é ideal para manter um conjunto dos K maiores elementos, pois ela sempre remove o menor elemento quando seu tamanho excede k.

O heap de mínimos armazenará pares (valor, frequência). O critério de comparação do heap será baseado na frequência (o segundo elemento do par), de modo que o elemento com a menor frequência esteja sempre no topo.

• Iteramos sobre o mapa de frequências.
• Para cada par (valor, frequência), o adicioanmos ao heap.
• Se o tamanho do heap exceder k, removemos o elemento do topo (que tem a menor frequência entre os k+1 elementos).
• Ao final da iteração, o heap conterá os k elementos com as maiores frequências.

Implementação em C++:

// Complexidade de tempo: O(N + M log K), onde M é o número de elementos únicos (M <= N)
// Complexidade de espaço: O(M)
#include <vector>
#include <unordered_map>
#include <queue>
#include <utility> // Para std::pair

class SolucaoFrequencia {
public:
    // Estrutura para comparar pares no heap de mínimos.
    // std::priority_queue é um heap de máximos por padrão.
    // Para um heap de mínimos, o operador() deve retornar 'true'
    // se 'a' tiver "maior prioridade" (ou seja, deve vir antes no heap) do que 'b'.
    // Para um min-heap de frequências, isso significa que 'a' tem uma frequência MENOR que 'b'.
    // Mas, como priority_queue usa `less` por padrão, para fazer um min-heap com `greater`,
    // ou seja, o topo é o menor, a comparação deve retornar true se o segundo elemento
    // de 'a' é MAIOR que o segundo elemento de 'b'.
    struct ComparadorMinHeap {
        bool operator()(const std::pair<int, int>& a, const std::pair<int, int>& b) {
            return a.second > b.second; // Elemento com MAIOR frequência vai para 'baixo' no heap
        }
    };

    std::vector<int> encontrarTopKFrequentes(const std::vector<int>& dados, int k) {
        // Passo 1: Contar a frequência de cada número
        std::unordered_map<int, int> contagemElementos;
        for (int numero : dados) {
            contagemElementos[numero]++;
        }

        // Passo 2: Usar um heap de mínimos para encontrar os K elementos mais frequentes
        // O heap armazenará pares {número, frequência}
        std::priority_queue<std::pair<int, int>,
                            std::vector<std::pair<int, int>>,
                            ComparadorMinHeap> minHeap;

        for (const auto& par : contagemElementos) {
            minHeap.push(par);
            // Se o tamanho do heap exceder K, remove o elemento com a menor frequência (topo)
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }

        // Passo 3: Extrair os elementos do heap
        std::vector<int> resultadoTopK;
        while (!minHeap.empty()) {
            resultadoTopK.push_back(minHeap.top().first);
            minHeap.pop();
        }
        // A ordem na saída não é especificada, então esta ordem é aceitável.
        return resultadoTopK;
    }
};