Stack·Cola·Heap

// =====================================================
// P-06 — Rectángulo mayor en histograma
// =====================================================
// IDEA: Stack Monotónico Creciente de índices.
//
// Invariante: el stack guarda índices cuyas alturas
// están en orden CRECIENTE de abajo a arriba.
//
// Cuando la barra actual es MENOR que el tope del stack,
// la barra del tope ya NO puede extenderse hacia la derecha.
// → Calculamos su área máxima y la removemos.
//
// Área de barra i: altura[i] × ancho
// Ancho = desde el nuevo tope del stack hasta i (exclusivo)
//
// Truco del centinela: agregar altura=0 al final para
// forzar el vaciado del stack y calcular las áreas finales.
//
// Complejidad: O(N) — cada índice entra y sale del stack una vez
// =====================================================
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int maxAreaHistograma(vector<int> alturas) {
    alturas.push_back(0); // centinela: fuerza el vaciado final del stack
    stack<int> st;       // guarda índices (no alturas directamente)
    int maxArea = 0;

    for (int i = 0; i < (int)alturas.size(); i++) {
        // Mientras la barra actual rompe la monotonía creciente
        while (!st.empty() && alturas[st.top()] > alturas[i]) {
            int altura = alturas[st.top()]; st.pop();

            // Ancho: si el stack quedó vacío, el rectángulo llega hasta 0
            // Si no, llega desde el nuevo tope hasta i
            int ancho = st.empty() ? i : (i - st.top() - 1);

            maxArea = max(maxArea, altura * ancho);
        }
        st.push(i); // mantener el stack monotónico
    }
    return maxArea;
}

int main() {
    // [2,1,5,6,2,3]: el rect más grande es 5×2=10 (barras 5 y 6)
    cout << maxAreaHistograma({2,1,5,6,2,3}) << "\n"; // 10
    cout << maxAreaHistograma({2,4})                 << "\n"; // 4
    cout << maxAreaHistograma({6,2,5,4,5,1,6})     << "\n"; // 12
}

// =====================================================
// P-07 — Mediana en tiempo real con dos Heaps
// =====================================================
// IDEA: partir el stream en dos mitades con dos heaps:
//
//   maxHeap → mitad INFERIOR (el mayor es el tope)
//   minHeap → mitad SUPERIOR (el menor es el tope)
//
//   Visualización para [1, 3, 5, 7, 9]:
//     maxHeap:  1  3          ← tope = 3
//     minHeap:     5  7  9   ← tope = 5
//     Mediana = 5 (centro exacto)
//
// INVARIANTE: |maxHeap| == |minHeap|  o  |maxHeap| == |minHeap| + 1
//   → Si tamaños iguales: mediana = (tope_max + tope_min) / 2.0
//   → Si maxHeap tiene 1 extra: mediana = tope_max
//
// Inserción: O(log N)  |  getMedian: O(1)
// =====================================================
#include <iostream>
#include <queue>
using namespace std;

class MedianaStream {
    // Max-Heap: guarda la mitad inferior del stream
    priority_queue<int> maxHeap;

    // Min-Heap: guarda la mitad superior del stream
    priority_queue<int, vector<int>, greater<int>> minHeap;

public:
    void insertar(int num) {
        // Paso 1: asignar num al heap correcto
        // → Si num es ≤ al mayor de la mitad baja, va a maxHeap
        //   (o si maxHeap está vacío)
        if (maxHeap.empty() || num <= maxHeap.top())
            maxHeap.push(num);
        else
            minHeap.push(num);

        // Paso 2: rebalancear para mantener el invariante de tamaños
        // maxHeap puede tener a lo sumo 1 elemento más que minHeap
        if (maxHeap.size() > minHeap.size() + 1) {
            // maxHeap tiene demasiados: mover el mayor a minHeap
            minHeap.push(maxHeap.top()); maxHeap.pop();
        } else if (minHeap.size() > maxHeap.size()) {
            // minHeap tiene demasiados: mover el menor a maxHeap
            maxHeap.push(minHeap.top()); minHeap.pop();
        }
    }

    double mediana() const {
        if (maxHeap.size() == minHeap.size())
            return (maxHeap.top() + minHeap.top()) / 2.0; // promedio central
        return maxHeap.top(); // maxHeap tiene el elemento del medio
    }
};

int main() {
    MedianaStream ms;
    for (int num : {5, 15, 1, 3, 8, 7, 9, 2}) {
        ms.insertar(num);
        cout << "Insertar " << num
             << " → mediana: " << ms.mediana() << "\n";
    }
    // 5→5 | 15→10 | 1→5 | 3→4 | 8→5 | 7→6 | 9→7 | 2→6
}