Evaluación de Expresiones en Notación Polaca Inversa (RPN)

La Notación Polaca Inversa es un método de escritura de expresiones matemáticas donde los operadores siguen a sus operandos. Para resolver este problema de manera eficiente, se utiliza una estructura de datos de tipo pila (LIFO). El algoritmo consiste en iterar sobre los elementos: si encontramos un número, lo apilamos; si encontramos un operador, extraemos los dos últimos elementos, aplicamos la operación y devolvemos el resultado a la pila.

#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <stdexcept>

using namespace std;

class EvaluadorRPN {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> operandos;
        
        for (const string& t : tokens) {
            if (t == "+" || t == "-" || t == "*" || t == "/") {
                long long valorB = operandos.top();
                operandos.pop();
                long long valorA = operandos.top();
                operandos.pop();
                
                if (t == "+") operandos.push(valorA + valorB);
                else if (t == "-") operandos.push(valorA - valorB);
                else if (t == "*") operandos.push(valorA * valorB);
                else if (t == "/") operandos.push(valorA / valorB);
            } else {
                operandos.push(stoll(t));
            }
        }
        return static_cast<int>(operandos.top());
    }
};

Máximo en Ventana Deslizante mediante Colas Monotónicas

Para obtener el valor máximo en cada posición de una ventana que se deslpaza a través de un arreglo, una solución ingenua de O(n*k) no es óptima. Utilizando una cola de doble final (deque) para construir una "Cola Monotónica", podemos reducir la complejidad a O(n). La clave es mantener los elementos en la cola en orden descendente, eliminando aquellos que ya no pueden ser el máximo.

#include <vector>
#include <deque>

using namespace std;

class VentanaOptimizada {
private:
    class ColaMonotonica {
    public:
        deque<int> datos;

        void eliminar(int valor) {
            if (!datos.empty() && valor == datos.front()) {
                datos.pop_front();
            }
        }

        void insertar(int valor) {
            while (!datos.empty() && valor > datos.back()) {
                datos.pop_back();
            }
            datos.push_back(valor);
        }

        int obtenerMaximo() {
            return datos.front();
        }
    };

public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        ColaMonotonica q;
        vector<int> maximos;

        for (int i = 0; i < k; i++) {
            q.insertar(nums[i]);
        }
        maximos.push_back(q.obtenerMaximo());

        for (int i = k; i < nums.size(); i++) {
            q.eliminar(nums[i - k]);
            q.insertar(nums[i]);
            maximos.push_back(q.obtenerMaximo());
        }
        return maximos;
    }
};

Elementos más Frecuentes con Priority Queue

Identificar los K elemenots con mayor frecuencia requiere dos pasos: primero, contar las ocurrencias usando un mapa hash; segundo, seleccionar los elementos más frecuentes. Al usar un min-heap (cola de prioridad) de tamaño K, garantizmaos que solo conservamos los elementos con mayores frecuencias, logrando una eficiencia de O(n log k).

#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

class AnalizadorFrecuencia {
public:
    struct ComparadorFrec {
        bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
            return a.second > b.second; // Min-heap basado en frecuencia
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> conteo;
        for (int n : nums) {
            conteo[n]++;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, ComparadorFrec> minHeap;

        for (auto const& [num, freq] : conteo) {
            minHeap.push({num, freq});
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }

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