1. Pilha Mínima (Min Stack)

Descrição do Problema

Implementar uma estrutura de pilha que suporte as operações padrão (push, pop, top) e também retorne o menor elemento em tempo constante (O(1)). A solução não pode percorrer a pilha para encontrar o mínimo a cada chamada.

Análise do Algoritmo

A abordagem clássica utiliza duas pilhas: uma pilha principal (p1) para armazenar todos os elementos, e uma pilha auxiliar (p_min) para manter o histórico dos menores valores. A cada push, se o novo valor for menor ou igual ao topo de p_min, ele também é inserido em p_min. No pop, se o elemento removido de p1 for igual ao topo de p_min, removemos também o topo de p_min.

Detalhe importente: Valores iguais ao mínimo atual devem ser inseridos também na pilha auxiliar. Caso contrário, ao remover o último desses valores iguais, o menor deixaria de ser o correto. Por exemplo: inserções 4, 2, 2. Se apenas o primeiro 2 for colocado em p_min, ao remover o topo (2) de p1, removeríamos o 2 de p_min. O próximo elemento em p1 ainda é 2, mas p_min teria 4 no topo – incorreto. Por isso, inserimos também o segundo 2 em p_min.

Implementação

#include <stack>
using namespace std;

class PilhaMin {
public:
    PilhaMin() {}

    void empilhar(int val) {
        if (p1.empty()) {
            p1.push(val);
            pMin.push(val);
        } else {
            p1.push(val);
            if (val <= pMin.top())
                pMin.push(val);
        }
    }

    void desempilhar() {
        if (p1.top() == pMin.top())
            pMin.pop();
        p1.pop();
    }

    int topo() {
        return p1.top();
    }

    int obterMinimo() {
        return pMin.top();
    }

private:
    stack<int> p1;
    stack<int> pMin;
};

2. Percurso em Nível da Árvore Binária (Level Order Traversal)

Descrição do Problema

Dado um nó raiz de uma árvore binária, retornar os valores dos nós no percurso em nível, mas agrupados por nível em vetores separados (vetor de vetores).

Análise do Algoritmo

Utilizamos uma fila para realizar o percurso clássico em largura (BFS). A cada iteração, processamos exatamente o número de nós daquele nível (obtido pelo tamanho atual da fila). Para cada nó: removemos da fila, adicionamos seu valor a um vetor temporário (nivelAtual) e enfileiramos seus filhos (esquerdo e direito) se existirem. Ao final do processamento de um nível, adicionamos nivelAtual ao vetor de resultado. O processo termina quando a fila estiver vazia.

Cuidado: Tratar o caso de árvore vazia retornando um vetor vazio.

Implementação

#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<vector<int>> nivelOrdem(TreeNode* raiz) {
        if (!raiz) return {};

        vector<vector<int>> resultado;
        queue<TreeNode*> fila;
        fila.push(raiz);

        while (!fila.empty()) {
            int tamNivel = fila.size();
            vector<int> nivel;

            for (int i = 0; i < tamNivel; ++i) {
                TreeNode* no = fila.front();
                fila.pop();
                nivel.push_back(no->val);
                if (no->left) fila.push(no->left);
                if (no->right) fila.push(no->right);
            }
            resultado.push_back(nivel);
        }
        return resultado;
    }
};

3. Sequência de Empilhamento e Desempilhamento (Stack Push/Pop Sequence)

Descrição do Problema

Dadas duas sequências de inteiros (pushSeq e popSeq), determinar se a segunda sequência pode ser uma ordem de desempilhamento válida a partir de empilhamentos realizados na ordem da primeira sequência. Por exemplo: push = [1,2,3,4,5] e pop = [4,5,3,2,1] é válido (empilha 1,2,3,4; desempilha 4; empilha 5; desempilha 5,3,2,1).

Análise do Algoritmo

Simulamos o processo usando uma pilha. Mantemos um índice i sobre a sequência de desempilhamento. Percorremos a sequência de empilhamento: a cada elemento, empilhamos na pilha. Em seguida, enquanto a pilha não estiver vazia e o topo da pilha for igual ao elemento atual de desempilhamento (apontado por i), desempilhamos e avançamos i. Se ao final a pilha estiver vazia, a sequência é válida. Caso contrário, é inválida.

Variante: Podemos usar dois ponteiros para percorrer ambas as sequências simultaneamente, com uma lógica ligeiramente diferente (empilhar até achar o próximo a ser desempilhado, etc.). Apresentamos ambas as implementações.

Implementação (usando range-for)

#include <vector>
#include <stack>
using namespace std;

class Verificador {
public:
    bool sequenciaValida(vector<int>& pushSeq, vector<int>& popSeq) {
        stack<int> pilha;
        int j = 0; // índice para popSeq
        for (int x : pushSeq) {
            pilha.push(x);
            while (!pilha.empty() && pilha.top() == popSeq[j]) {
                pilha.pop();
                ++j;
            }
        }
        return pilha.empty();
    }
};

Implementação (usando dois ponteiros)

#include <vector>
#include <stack>
using namespace std;

class Verificador2 {
public:
    bool sequenciaValida(vector<int>& pushSeq, vector<int>& popSeq) {
        int i = 0, j = 0; // i para pushSeq, j para popSeq
        int n = pushSeq.size();
        stack<int> pilha;

        while (i < n) {
            // Empilha até encontrar o elemento que deve ser desempilhado
            while (i < n && (pilha.empty() || pilha.top() != popSeq[j])) {
                pilha.push(pushSeq[i]);
                ++i;
            }
            // Desempilha enquanto o topo coincidir
            while (!pilha.empty() && pilha.top() == popSeq[j]) {
                pilha.pop();
                ++j;
            }
        }
        return pilha.empty();
    }
};