Monotonic Stack y Deque

Una Monotonic Stack es una Stack que mantiene sus elementos siempre en orden creciente o decreciente. El truco: cuando intentas agregar un elemento que rompe el orden, primero sacas todos los elementos que no cumplen el criterio. Este proceso de "popping" es lo que resuelve los problemas: cada elemento que se saca del stack cuando llega uno más grande es el elemento que tiene ese "siguiente elemento mayor" que buscas.

El problema "Next Greater Element" ilustra el patrón: para cada elemento de un array, encontrar el primer elemento a su derecha que sea mayor. La solución naive O(n²) usa dos loops anidados.

Con Monotonic Stack es O(n): recorres el array, para cada elemento sacas del stack todos los menores (para ellos, el elemento actual es su "siguiente mayor"), y empujas el elemento actual. El Deque (double-ended queue) extiende esto para ventanas deslizantes de máximos, un patrón de Leetcode difícil.

// Siguiente elemento mayor - O(n) con Monotonic Stack
function siguienteMayor(nums) {
  const resultado = new Array(nums.length).fill(-1);
  const pila = []; // Guarda índices, no valores
  
  for (let i = 0; i < nums.length; i++) {
    // Mientras la pila no esté vacía y el elemento actual
    // es mayor que el tope de la pila
    while (pila.length > 0 && nums[i] > nums[pila.at(-1)]) {
      const idx = pila.pop();
      resultado[idx] = nums[i]; // El actual es el "siguiente mayor"
    }
    pila.push(i);
  }
  
  return resultado;
}

console.log(siguienteMayor([2,1,2,4,3]));
// [4, 2, 4, -1, -1]

// Problema: Largest Rectangle in Histogram
function largestRectangle(heights) {
  const pila = [-1];
  let maxArea = 0;
  
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];
    while (pila.at(-1) !== -1 && heights[pila.at(-1)] >= h) {
      const alto = heights[pila.pop()];
      const ancho = i - pila.at(-1) - 1;
      maxArea = Math.max(maxArea, alto * ancho);
    }
    pila.push(i);
  }
  return maxArea;
}

console.log(largestRectangle([2,1,5,6,2,3])); // 10

// Sliding Window Maximum con Deque - O(n)
// Máximo en cada ventana de tamaño k
function ventanaMaxima(nums, k) {
  const deque = []; // Índices, decreciente por valor
  const resultado = [];
  
  for (let i = 0; i < nums.length; i++) {
    // Eliminar elementos fuera de la ventana
    if (deque[0] === i - k) deque.shift();
    // Mantener orden decreciente
    while (deque.length > 0 && nums[deque.at(-1)] < nums[i]) deque.pop();
    deque.push(i);
    if (i >= k - 1) resultado.push(nums[deque[0]]);
  }
  return resultado;
}

console.log(ventanaMaxima([1,3,-1,-3,5,3,6,7], 3));
// [3,3,5,5,6,7]