Evaluación de Notación Polaca Inversa (Problema 150)

Este problema consiste en calcualr el resultado de una expresión aritmética representada en notación polaca inversa. Conceptualmente, este proceso equivale a un recorrido post-orden en un árbol binario. La implementación requiere una pila para almacenar los operandos. Es crucial tener en cuenta el orden de los operandos durante la división y la resta (el segundo elemento extraído es el dividendo o minuendo). Además, se debe manejar la conversión de cadenas a enteros largos para evitar desbordamientos.

class Solucion {
public:
    int evaluarRPN(vector<string>& expresion) {
        stack<long long> pilaOperandos; 
        for (const string& token : expresion) {
            if (token == "+" || token == "-" || token == "*" || token == "/") {
                long long operandoB = pilaOperandos.top();
                pilaOperandos.pop();
                long long operandoA = pilaOperandos.top();
                pilaOperandos.pop();
                
                if (token == "+") pilaOperandos.push(operandoA + operandoB);
                else if (token == "-") pilaOperandos.push(operandoA - operandoB);
                else if (token == "*") pilaOperandos.push(operandoA * operandoB);
                else if (token == "/") pilaOperandos.push(operandoA / operandoB);
            } else {
                pilaOperandos.push(stoll(token));
            }
        }
        return static_cast<int>(pilaOperandos.top());
    }
};

Máximo en Ventana Deslizante (Problema 239)

Para obtener el valor máximo en cada ventana deslizante de tamaño k, se utiliza una cola monotónica decreciente. La estructura debe mantener dos invariantes principales durante las operaciones de entrada y salida. Al eliminar un elemento, solo se afecta la cola si el valor saliente coincide con el frente de la cola monotónica. Al insertar, se deben remover todos los elementos menores que el nuevo valor desde la parte trasera, garantizando que el frente siempre contenga el máximo actual.

class Solucion {
private:
    class ColaMonotonic {
    public:
        deque<int> buffer; 
        
        void eliminar(int valor) {
            if (!buffer.empty() && valor == buffer.front()) {
                buffer.pop_front();
            }
        }
        
        void insertar(int valor) {
            while (!buffer.empty() && valor > buffer.back()) {
                buffer.pop_back();
            }
            buffer.push_back(valor);
        }
        
        int obtenerMaximo() {
            return buffer.front();
        }
    };
public:
    vector<int> maxVentanaDeslizante(vector<int>& datos, int k) {
        ColaMonotonic cola;
        vector<int> resultados;
        for (int i = 0; i < k; ++i) {
            cola.insertar(datos[i]);
        }
        resultados.push_back(cola.obtenerMaximo());
        
        for (int i = k; i < datos.size(); ++i) {
            cola.eliminar(datos[i - k]);
            cola.insertar(datos[i]);
            resultados.push_back(cola.obtenerMaximo());
        }
        return resultados;
    }
};

Elementos Más Frecuentes (Problema 347)

Este algoritmo requiere identificar los k elementos con mayor frecuencia de aparición. La solución combina un mapa hash para el conteo y una cola de prioridad (heap) para el ordenamiento parcial. Se utiliza un heap de tamaño mínimo (min-heap) de tamaño fijo k. Esto permite que, al iterar sobre las frecuencias, los elementos menos frecuentes sean descartados automáticamente, menteniendo únicamente los k más relevantes en la estructura.

class Solucion {
public:
    struct ComparadorMinimo {
        bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
            return a.second > b.second;
        }
    };

    vector<int> topKFrecuentes(vector<int>& entrada, int k) {
        unordered_map<int, int> conteo;
        for (int num : entrada) {
            conteo[num]++;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, ComparadorMinimo> heap;

        for (auto& par : conteo) {
            heap.push(par);
            if (heap.size() > k) {
                heap.pop();
            }
        }

        vector<int> resultado(k);
        for (int i = k - 1; i >= 0; --i) {
            resultado[i] = heap.top().first;
            heap.pop();
        }
        return resultado;
    }
};