Índice

1. Temperaturas diarias (Pila monótona clásica pura)
2. Siguiente elemento mayor I (Hash + Pila monótona)
3. Siguiente elemento mayor II (Arreglo circular)
4. Recoger agua (Buscar ambos lados más altos)
5. Rectángulo más grande en histograma (Buscar ambos lados más bajos)

Principio: Los valores almacenados en la pila mantienen la monotonicidad, sirve para guardar elementos traversed previamente que están pendientes de usar.

1. Temperaturas diarias (Pila monótona clásica purra)

Problema original LeetCode 739.

vector<int> dailyTemperatures(vector<int>& temperaturas)
{
    stack<int> pila;
    vector<int> resultado(temperaturas.size(), 0);
    pila.push(0);
    for (int i = 1; i < temperaturas.size(); i++)
    {
        if (temperaturas[i] <= temperaturas[pila.top()])
        {
            pila.push(i);
        }
        else
        {
            while (!pila.empty() && temperaturas[i] > temperaturas[pila.top()])
            {
                resultado[pila.top()] = i - pila.top();
                pila.pop();
            }
            pila.push(i);
        }
    }
    return resultado;
}

2. Siguiente elemento mayor I (Hash + Pila monótona)

Problema original LeetCode 496.

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2)
{
    unordered_map<int, int> mapeo;
    for (int i = 0; i < nums1.size(); i++)
    {
        mapeo[nums1[i]] = i;
    }
    vector<int> resultado(nums1.size(), -1);
    stack<int> pila;
    pila.push(0);
    for (int i = 1; i < nums2.size(); i++)
    {
        if (nums2[i] <= nums2[pila.top()])
        {
            pila.push(i);
        }
        else
        {
            while (!pila.empty() && nums2[i] > nums2[pila.top()])
            {
                if (mapeo.count(nums2[pila.top()]))
                {
                    resultado[mapeo[nums2[pila.top()]]] = nums2[i];
                    pila.pop();
                }
                else
                {
                    pila.pop();
                }
            }
            pila.push(i);
        }
    }
    return resultado;
}

3. Siguiente elemento mayor II (Arreglo circular)

Problema original LeetCode 503.

Se模拟 el proceso circular mediante módulo.

vector<int> nextGreaterElements(vector<int>& numeros)
{
    stack<int> pila;
    vector<int> resultado(numeros.size(), -1);
    pila.push(0);
    for (int i = 1; i < numeros.size() * 2; i++)
    {
        if (numeros[i % numeros.size()] <= numeros[pila.top()])
        {
            pila.push(i % numeros.size());
        }
        else
        {
            while (!pila.empty() && numeros[i % numeros.size()] > numeros[pila.top()])
            {
                resultado[pila.top()] = numeros[i % numeros.size()];
                pila.pop();
            }
            pila.push(i % numeros.size());
        }
    }
    return resultado;
}

4. Recoger agua (Buscar ambos lados más altos)

Problema original LeetCode 42.

int trap(vector<int>& altura)
{
    int acumulador = 0;
    stack<int> pila;
    pila.push(0);
    for (int i = 1; i < altura.size(); i++)
    {
        if (altura[i] < altura[pila.top()])
        {
            pila.push(i);
        }
        else if (altura[i] == altura[pila.top()]) // Cuando son iguales, no hay diferencia de altura, no afecta el resultado
        {
            pila.pop();
            pila.push(i);
        }
        else
        {
            while (!pila.empty() && altura[i] > altura[pila.top()]) // Se encontró una columna hundida, buscar columnas más altas a ambos lados
            {
                int posicionMedia = pila.top(); // Posición de la columna hundida
                pila.pop();
                if (!pila.empty())
                {
                    // Altura = min(altura de la primera columna más alta a la izquierda, altura de la primera columna más alta a la derecha) - altura de la columna hundida
                    int alto = min(altura[pila.top()], altura[i]) - altura[posicionMedia];
                    // Ancho = posición de la columna derecha - posición de la columna izquierda - 1
                    int ancho = i - pila.top() - 1;
                    // Área = altura * ancho (cálculo horizontal, acumulativo)
                    acumulador += alto * ancho;
                }
            }
            pila.push(i);
        }
    }
    return acumulador;
}

5. Rectángulo más grande en histograma (Buscar ambos lados más bajos)

Problema original LeetCode 84.

int largestRectangleArea(vector<int>& alturas)
{
    int maximo = 0;
    // Agregar 0 al inicio y final para evitar bucle infinito
    alturas.insert(alturas.begin(), 0);
    alturas.push_back(0);
    stack<int> pila;
    pila.push(0);
    for (int i = 1; i < alturas.size(); i++)
    {
        if (alturas[i] >= alturas[pila.top()])
        {
            pila.push(i);
        }
        else
        {
            // Encontrar la primera columna más baja a la izquierda y derecha de la columna突出
            while (!pila.empty() && alturas[i] < alturas[pila.top()])
            {
                int intermedio = pila.top();
                pila.pop();
                if (!pila.empty())
                {
                    int alto = alturas[intermedio]; // La altura es la de la columna突出 actual
                    int ancho = i - pila.top() - 1; // El ancho es la diferencia de posiciones menos 1
                    maximo = max(maximo, alto * ancho);
                }
            }
            pila.push(i);
        }
    }
    return maximo;
}