Entrevista de programación: ¿Cómo encontrar el rectángulo más grande en un histograma?

Problema y escenarios aplicables

Dado heights, cada valor representa una barra de histograma de ancho 1. Un rectángulo válido abarca una o más barras consecutivas, comienza en la línea base y no puede ser más alto que la barra más baja en ese tramo. Devuelve su área máxima.

heights = [2, 1, 5, 6, 2, 3]
answer = 10

El mejor rectángulo cubre los índices 2..3: su altura es 5, el ancho es 2 y el área es 10. Las restricciones estándar son 1 <= heights.length <= 100000 y 0 <= heights[i] <= 10000. Este artículo también define que una entrada vacía devuelve 0. Bajo los límites estándar, el área es como máximo 10^9, lo cual es representable exactamente por el tipo number de JavaScript.

El material actual de preparación para entrevistas en inglés y una solución pública independiente en chino presentan este problema exacto como un ejercicio de pila monótona. El problema original y una guía actual de DSA utilizan el mismo modelo de ancho 1 y las mismas restricciones. Eso respalda tratarlo como una pregunta representativa de coding sin atribuirla a una empresa ni afirmar una frecuencia inverificable.

Qué evalúa el entrevistador

La primera señal es si puedes modelar cada rectángulo posible sin enumerar cada par de límites. Para cualquier altura elegida, el mejor rectángulo se extiende hasta la primera barra estrictamente más baja en cada lado. Eso convierte un problema con apariencia geométrica en consultas de límites menores más cercanos.

La segunda señal es si puedes deducir la estructura de datos. Una pila de alturas crecientes mantiene las barras cuyo límite derecho aún se desconoce. Cuando llega una barra más baja, cierra uno o más de esos rectángulos. El índice actual es su primera posición más baja a la derecha; el inicio almacenado con cada barra ya codifica qué tan lejos a la izquierda puede extenderse.

La tercera señal es la corrección bajo duplicados y límites. Las alturas iguales no deben crear entradas competidoras con inicios diferentes. Las barras que quedan en la pila al final todavía necesitan un límite derecho. Una implementación sólida hace explícitas ambas reglas en lugar de depender de una fórmula de ancho memorizada.

Por último, el bucle anidado while necesita un análisis amortizado. Una iteración puede desapilar muchas entradas, pero cada entrada se apila una vez y se desapila una vez. El número total de operaciones de pila es lineal.

Preguntas de aclaración antes de responder

• ¿Cada barra tiene un ancho de 1? Sí. Los anchos variables cambian tanto el límite izquierdo almacenado como la fórmula del área.
• ¿El rectángulo debe usar barras consecutivas? Sí. Un rectángulo no puede omitir una barra baja en el medio.
• ¿Las alturas pueden ser cero o repetidas? Sí. El cero separa rectángulos positivos; las alturas iguales requieren una regla de pila consistente.
• ¿La entrada puede estar vacía? El problema estándar la excluye, mientras que esta implementación devuelve 0 como una extensión documentada.
• ¿Solo devolvemos el área? Sí. Devolver las coordenadas requiere retener el inicio, fin y altura ganadores más una regla de desempate.
• ¿Puede la función mutar la entrada? No es necesaria ninguna mutación; el centinela es virtual en lugar de ser agregado al arreglo.
• ¿Podría desbordarse el área? No bajo las restricciones indicadas. Un contrato de producción más grande debería calcular su límite y usar bigint o un entero más amplio donde sea necesario.
• ¿Se requiere tiempo lineal? Sí. Una línea base de O(n^2) es útil para la deducción y pruebas, pero no suficiente para las restricciones objetivo.

Estructura de respuesta en 30 segundos

“Para una barra de altura h, su rectángulo válido más ancho termina justo antes de la primera barra más baja en cada lado. Escaneo de izquierda a derecha con una pila de pares (start, height) en orden de altura estrictamente creciente. Cuando la altura actual es menor que el tope de la pila, el índice actual es el primer límite más bajo a la derecha de esa barra superior, así que la desapilo y calculo height * (right - start). Llevo el start desapilado hacia la izquierda porque la barra más baja actual puede extenderse a través de cada barra más alta recién removida. Mantengo la entrada anterior cuando las alturas son iguales. Un cero virtual al final cierra todos los rectángulos restantes. Cada entrada se apila y se desapila a lo sumo una vez, por lo que el tiempo y el espacio auxiliar son O(n) y O(n).”

Análisis detallado paso a paso

Paso 1: Establecer una línea base correcta.

Para cada intervalo [left, right], rastrea su altura mínima. Su rectángulo de ancho completo más grande tiene un área de:

min(heights[left..right]) * (right - left + 1)

Extender right mientras se mantiene el mínimo acumulado produce un oráculo de tiempo O(n^2) y espacio O(1). Es demasiado lento para n = 100000, pero es excelente para verificar una solución optimizada en entradas aleatorias pequeñas.

Paso 2: Invertir la enumeración.

En lugar de pedir el mínimo de cada intervalo, elige una barra como la altura limitante del rectángulo. Si las posiciones estrictamente más bajas más cercanas son leftShorter y rightShorter, entonces la barra puede cubrir:

(leftShorter + 1) .. (rightShorter - 1)
width = rightShorter - leftShorter - 1

Este es el rectángulo más ancho para esa altura limitante. La respuesta global es el máximo sobre todos esos candidatos.

Paso 3: Mantener las barras no resueltas en orden creciente.

La pila almacena { start, height }. Las alturas son estrictamente crecientes. start es el índice más temprano desde el cual esa altura se ha mantenido válida después de que se eliminaron todas las barras más altas previamente cerradas. Una nueva barra más alta comienza en su propio índice. Una nueva barra más baja cierra las entradas más altas e hereda el inicio desapilado más temprano.

Para [2, 1, 5, 6, 2, 3], la altura 2 en el índice 4 primero desapila 6, produciendo 6 * 1, y luego desapila 5, produciendo 5 * 2 = 10. Hereda el inicio 2, porque la altura 2 puede cubrir las dos barras más altas. La altura existente 1 permanece debajo de ella y detiene una mayor extensión.

Paso 4: Definir igualdad y finalización.

Si la altura actual es igual a la altura del tope, mantén la entrada más antigua. Las dos barras ofrecen la misma altura, pero la más antigua tiene un inicio anterior y, por lo tanto, nunca produce un mejor rectángulo más estrecho. Una altura virtual 0 en el índice n cierra todas las entradas positivas sin mutar la entrada ni duplicar la lógica de limpieza.

Paso 5: Implementar la invariante y demostrar el cálculo al desapilar.

interface StackBar {
  start: number
  height: number
}

export function largestRectangleArea(heights: number[]): number {
  const stack: StackBar[] = []
  let maxArea = 0

  for (let right = 0; right <= heights.length; right += 1) {
    const height = right === heights.length ? 0 : heights[right]
    let start = right

    while (stack.length > 0 && stack[stack.length - 1].height > height) {
      const bar = stack.pop()!
      maxArea = Math.max(maxArea, bar.height * (right - bar.start))
      start = bar.start
    }

    const top = stack[stack.length - 1]
    if (height > 0 && (!top || top.height < height)) {
      stack.push({ start, height })
    }
  }

  return maxArea
}

La demostración sigue tres invariantes antes de cada paso del escaneo:

1. Las alturas de la pila son estrictamente crecientes.
2. Para cada entrada, cada barra procesada desde start hasta right - 1 es al menos de su altura.
3. Ninguna barra procesada estrictamente más baja se encuentra dentro de ese intervalo; de lo contrario, la entrada ya habría sido desapilada.

Cuando llega una altura menor, las invariantes 2 y 3 muestran que la entrada desapilada puede extenderse a través de right - 1, mientras que la barra actual demuestra que no puede extenderse hasta right. Su ancho máximo es, por lo tanto, exactamente right - start, por lo que el área calculada está completa. Pasar el inicio desapilado a la altura actual es seguro porque la altura actual es menor que cada altura eliminada. Omitir una altura igual es seguro porque la entrada igual retenida comienza no más tarde. El centinela cierra cada entrada que no tiene una barra real más baja a su derecha. Por lo tanto, se considera el rectángulo máximo de cada altura limitante posible, y maxArea es el óptimo.

Paso 6: Verificar casos borde y complejidad.

Usa casos fijos que pongan a prueba diferentes invariantes:

Para una evidencia más sólida, compara el resultado de la pila con el oráculo cuadrático en muchos arreglos aleatorios pequeños. La implementación anterior se verificó contra siete casos fijos y 20,000 arreglos aleatorios de longitud 0..8 con alturas 0..7. Esto es evidencia ejecutable, no un reemplazo de demostración; las invariantes explican todas las entradas posibles.

Cada altura positiva se apila a lo sumo una vez y se desapila a lo sumo una vez, por lo que el tiempo total es O(n). Una entrada estrictamente creciente retiene las n entradas hasta el centinela, dando un espacio auxiliar en el peor caso de O(n).

Respuesta de muestra de alta calidad

“Primero establecería un oráculo cuadrático: para cada límite izquierdo, extender el límite derecho y mantener la altura mínima. Eso comprueba cada intervalo posible, pero es demasiado lento para 100,000 barras. La pregunta recurrente es qué tan lejos puede extenderse una altura elegida antes de que una barra más baja la bloquee, lo que apunta a límites menores más cercanos y a una pila monótona.

Mi pila almacena el inicio válido más temprano junto con cada altura no resuelta, y sus alturas son estrictamente crecientes. En el índice right, desapilo mientras el tope sea más alto que la barra actual. El índice actual es la primera posición inválida de la barra desapilada, por lo que su área máxima es bar.height * (right - bar.start). Paso su inicio a la altura actual porque esa barra más baja puede cubrir todas las barras más altas recién eliminadas. Si la altura es igual al tope de la pila, mantengo la entrada anterior en lugar de apilar un duplicado. Un cero virtual al final cierra el sufijo restante.

La invariante de la pila garantiza que cada barra entre el inicio de una entrada y la posición actual sea lo suficientemente alta. La barra actual más baja hace que el límite derecho calculado sea definitivo. Cada entrada se apila y se desapila a lo sumo una vez, dando un tiempo de O(n) y un espacio en el peor caso de O(n). Probaría alturas iguales, arreglos crecientes y decrecientes, ceros, una entrada vacía bajo este contrato extendido y compararía casos pequeños aleatorios con el oráculo cuadrático.”

Errores comunes

Cada fallo tiene una causa y corrección específicas:

• Usar right - start + 1 después de un desapilamiento → right ya es la primera posición inválida → Usa right - start.
• Olvidar el vaciado final → los sufijos crecientes nunca se evalúan → Escanea un cero virtual.
• Apilar cada altura igual → la corrección queda atada a una regla de desapilamiento más delicada → Mantén la entrada igual más temprana.
• Afirmar que el bucle interno hace que el tiempo sea cuadrático → cada entrada solo se puede desapilar una vez → Da el recuento amortizado.
• Agregar un centinela a heights → quienes llaman observan mutación → Calcula el centinela virtualmente.

Análisis detallado de preguntas de seguimiento

Pregunta de seguimiento 1: ¿Cómo se devuelven los límites del rectángulo?

Siempre que un área mejore, guarda { start: bar.start, end: right - 1, height: bar.height }. Define los desempates antes de programar: preferir el rectángulo más a la izquierda, el rectángulo más ancho o el rectángulo más alto. El área por sí sola no determina una respuesta única.

Pregunta de seguimiento 2: ¿Qué pasa si las barras tienen anchos variables?

Reemplaza el ancho de índice con sumas prefijas de anchos físicos. Las entradas de la pila deben retener la coordenada horizontal más temprana, y el área desapilada se convierte en height * (currentX - startX). Las barras de ancho cero y los anchos negativos inválidos necesitan un contrato explícito.

Pregunta de seguimiento 3: ¿Cómo se extiende esto a una matriz binaria?

Trata cada fila como la base de un histograma. Para cada columna, incrementa su altura cuando la celda actual sea 1; de lo contrario, reiníciala a 0; ejecuta el algoritmo del histograma después de cada fila. Para una matriz de m × n, el tiempo es O(mn) y el espacio auxiliar es O(n).

Pregunta de seguimiento 4: ¿Se puede mantener la respuesta exacta para un flujo de datos (stream)?

La pila puede procesar barras en línea, pero los rectángulos que aún están abiertos en el borde derecho del stream no son definitivos. Una instantánea puede calcular sus áreas temporales usando la longitud actual sin desapilarlos. El estado exacto puede crecer hasta O(n) en un stream estrictamente creciente; un algoritmo exacto de memoria fija no se deduce de esta invariante.

Pregunta de seguimiento 5: ¿Qué pasa si la entrada es demasiado grande para la memoria de una sola máquina?

Los máximos independientes de cada bloque son insuficientes porque el rectángulo ganador puede cruzar los límites del bloque. Un resumen distribuido debe preservar suficiente estructura de altura en los límites para fusionar bloques adyacentes, lo cual en sí mismo puede ser lineal en un bloque monótono. Menciona ese riesgo de cota inferior antes de prometer un resumen de fusión de tamaño constante.

Pregunta de seguimiento 6: ¿Cuándo es preferible un enfoque diferente?

El oráculo cuadrático es mejor para la verificación con entradas pequeñas. Dividir y conquistar alrededor del mínimo es útil para deducir la recurrencia, pero un escaneo lineal para cada mínimo se convierte en O(n^2) en una entrada ordenada. Una estructura de datos de mínimo de rango (RMQ) puede admitir otras consultas repetidas, pero para este único máximo estático, la pila monótona es más simple y asintóticamente óptima.