10 marzo 2025

Monotonic Stack

Uno stack monotono è una struttura dati basata su uno stack che mantiene i suoi elementi in ordine crescente o decrescente. È particolarmente utile per problemi che richiedono di trovare in modo efficiente l’elemento successivo maggiore o minore.

A differenza di uno stack tradizionale, che segue il principio Last In, First Out (LIFO) senza alcuna restrizione sull’ordinamento, uno stack monotono mantiene un ordine ordinato tra i suoi elementi, rendendolo ideale per determinati algoritmi greedy e problemi di finestra scorrevole.

Perché usare uno stack monotono?

Uno stack monotono è utile quando si risolvono problemi che coinvolgono:

Questa tecnica è ampiamente utilizzata in problemi relativi ai prezzi delle azioni, tendenze delle temperature, calcolo dell’area di un istogramma e problemi di minimi/massimi nelle finestre scorrevoli.

Tipi di stack monotoni

  1. Stack monotono crescente

    • Mantiene gli elementi in ordine crescente.
    • Viene utilizzato per trovare l’elemento successivo minore per ciascun elemento in un array.
    • Se un elemento è minore rispetto all’elemento in cima allo stack, si rimuovono gli elementi dallo stack fino a mantenere l’ordine.

  2. Stack monotono decrescente

    • Mantiene gli elementi in ordine decrescente.
    • Viene utilizzato per trovare in modo efficiente l’elemento successivo maggiore.
    • Se un elemento è maggiore rispetto all’elemento in cima allo stack, si rimuovono gli elementi dallo stack fino a mantenere l’ordine.

Implementazione in JavaScript

1. Elemento Successivo Maggiore usando uno Stack Monotono Decrescente

function nextGreaterElement(arr) {
  let stack = [];
  let result = new Array(arr.length).fill(-1);

  for (let i = 0; i < arr.length; i++) {
    while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
      let index = stack.pop();
      result[index] = arr[i];
    }
    stack.push(i);
  }
  return result;
}

console.log(nextGreaterElement([2, 1, 5, 3, 6, 4, 8])); // Output: [5, 5, 6, 6, 8, 8, -1]

2. Elemento Successivo Minore usando uno Stack Monotono Crescente

function nextSmallerElement(arr) {
  let stack = [];
  let result = new Array(arr.length).fill(-1);

  for (let i = 0; i < arr.length; i++) {
    while (stack.length > 0 && arr[stack[stack.length - 1]] > arr[i]) {
      let index = stack.pop();
      result[index] = arr[i];
    }
    stack.push(i);
  }
  return result;
}

console.log(nextSmallerElement([4, 5, 2, 10, 8])); // Output: [2, 2, -1, 8, -1]

3. Il più Grande Rettangolo nell’Istogramma usando uno Stack Monotono

function largestRectangleArea(heights) {
  let stack = [];
  let maxArea = 0;
  heights.push(0); // ensure all indexes are processed

  for (let i = 0; i < heights.length; i++) {
    while (stack.length > 0 && heights[stack[stack.length - 1]] > heights[i]) {
      let height = heights[stack.pop()];
      let width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }
  return maxArea;
}

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

Analisi della Complessità

Complessità Temporale: in tutti i casi, poiché ogni elemento viene inserito e rimosso dallo stack al massimo una volta.

Complessità Spaziale: nel caso peggiore, se tutti gli elementi sono memorizzati nello stack.

Quando usare uno Stack Monotono?