Entrevista técnica de programación: Resolver Next Greater Element II con una pila monótona

Qué evalúa el entrevistador

Dado un arreglo circular de enteros, devuelva el primer valor estrictamente mayor encontrado en el sentido de las agujas del reloj para cada elemento, o -1 cuando no exista ninguno. Las entradas pueden contener duplicados, secuencias monótonas o todos los valores iguales.

Restricciones y casos límite

“Mayor” es estricto; un valor igual no puede resolver un índice.
El índice i busca desde i+1 hasta n-1, y luego se envuelve hacia 0.
Cada posición recibe a lo sumo una respuesta; la segunda pasada no debe sobrescribir un resultado resuelto.
Apunte a un tiempo O(n) y un espacio extra de O(n).

Estructura de respuesta de 30 segundos

“Mantengo una pila decreciente de índices que todavía están esperando un valor mayor. Escaneo un arreglo duplicado virtual: un valor actual estrictamente mayor desapila y resuelve las entradas de la pila; los índices entran solo durante la primera pasada, mientras que la segunda pasada proporciona candidatos de envoltura circular. Cada índice se apila y desapila a lo sumo una vez, por lo que el algoritmo es lineal”.

Almacenar posiciones que esperan una respuesta

Almacene índices en lugar de valores para que el algoritmo pueda escribir resultados y preservar posiciones duplicadas. Mantenga los valores no crecientes desde el fondo de la pila hacia el tope. Un valor actual mayor resuelve cada valor en espera menor que pueda desapilar.

Convertir la envoltura circular en un escaneo acotado

Lea nums[i % n] para i desde 0 hasta 2n-2. Cuando i esté por debajo de n, apile el índice después de resolver las entradas anteriores; en la segunda visita, úselo únicamente para resolver la pila restante. Esto evita copiar el arreglo y previene un bucle infinito.

Manejar la comparación estricta y los duplicados

Desapile solo cuando nums[current] > nums[stackTop]. Mayor o igual permitiría incorrectamente que valores iguales se resuelvan entre sí; menor que rompe la invariante decreciente. Los índices no resueltos conservan el -1 inicial.

Preguntas aclaratorias antes de responder

¿Es “siguiente” estrictamente mayor? Permitir mayor o igual cambia la condición de desapilado y el comportamiento ante duplicados.
¿Puede el arreglo estar vacío? Defina la forma del valor de retorno antes de implementar.
¿El resultado debe contener valores o índices? Las distancias y los índices requieren diferentes cálculos de envoltura circular.

Análisis detallado paso a paso

Inicialice cada resultado en -1 y mantenga una pila vacía. Para la posición virtual i, establezca index = i % n y lea value = nums[index]. Primero resuelva los índices de la pila cuyo valor sea menor; cuando i esté por debajo de n, apile index porque aún no ha tenido su búsqueda completa en el sentido de las agujas del reloj. La segunda pasada nunca apila, por lo que cada índice entra una sola vez.

text

result = [-1] * n
stack = []
for i in range(2 * n - 1):
    index = i % n
    while stack and nums[stack[-1]] < nums[index]:
        result[stack.pop()] = nums[index]
    if i < n:
        stack.append(index)

Para [1,2,1], el último 1 ve a 2 después de envolver circularmente, mientras que 2 no tiene ningún valor estrictamente mayor. Los índices restantes en la pila retienen correctamente -1.

Respuesta modelo de alta calidad

“Almaceno los índices que no han encontrado una respuesta en una pila no creciente. Escaneo lógicamente el arreglo dos veces con i % n; un valor actual estrictamente mayor que el tope de la pila desapila y resuelve ese índice. Apilo cada índice únicamente en su primera visita, de modo que la segunda pasada maneja la envoltura circular sin duplicación. Los resultados comienzan en -1, lo que hace que los arreglos de elementos iguales y las respuestas faltantes sean correctos. Cada índice se apila y desapila a lo sumo una vez, lo que da un tiempo O(n) y un espacio O(n)”.

Errores comunes

Copiar el arreglo tres veces para manejar la circularidad.
Apilar índices nuevamente en la segunda pasada, causando trabajo duplicado o sobrescrituras.
Usar mayor o igual y tratar a los valores iguales como mayores.
Escanear desde la derecha sin definir una invariante de pila, por lo que la respuesta no es el primer valor mayor.
Dejar los resultados sin inicializar e intentar reparar la pila después del escaneo.

Síntomas de fallo y soluciones

Si [1,1,1] devuelve un valor distinto de -1, la regla de igualdad es incorrecta. Si el último 1 en [1,2,1] devuelve -1, se omitió la envoltura circular. Rastree los índices y valores de la pila y asegúrese de que cada desapilado tenga un valor actual estrictamente mayor.

Implementación para producción

Use un tipo de índice lo suficientemente amplio para la entrada. Evite copiar el arreglo cuando la memoria sea limitada. Para devolver la distancia, calcule (index - j + n) % n al resolver el índice j, y defina si se permite una distancia cero.

Lista de verificación de validación

Pruebe con entrada vacía, un solo elemento, todos iguales, estrictamente creciente, estrictamente decreciente, picos repetidos y arreglos aleatorios. Para entradas pequeñas, compare con una referencia O(n²) que escanee en el sentido de las agujas del reloj desde cada índice, utilizando pruebas diferenciales aleatorias.

Preguntas de seguimiento y respuestas

¿Por qué cada índice solo se puede desapilar una vez?

Una vez que un índice encuentra su primer valor estrictamente mayor, sale de la pila. Un elemento más lejano no puede ser el primer valor mayor. Cada índice entra una vez y sale una vez, por lo que el desapilado total es O(n).

¿Qué cambia para mayor o igual?

Desapile cuando el valor actual sea menor o igual al tope de la pila, luego defina cómo deben comportarse los valores iguales alrededor del círculo, incluyendo si un elemento puede resolverse a sí mismo en una visita posterior.

¿Qué ocurre si la entrada es un flujo continuo e infinito que se repite?

No espere a que cada posición se resuelva. Establezca una ventana de observación finita o un tiempo límite. Para un arreglo fijo, dos pasadas cubren todos los posibles candidatos posteriores.

Rúbrica de evaluación

Invariante: explica que la pila decreciente contiene índices esperando respuestas.
Manejo circular: utiliza dos pasadas acotadas sin copiar ni entrar en bucles infinitos.
Límite de duplicados: usa comparación estricta y preserva los valores no resueltos -1.
Complejidad: proporciona tiempo O(n) y espacio extra O(n).
Verificación: incluye un oráculo O(n²) y pruebas aleatorias, de duplicados y monótonas.

Verificación de cumplimiento

Confirme que la invariante de la pila, los límites circulares y la afirmación de complejidad se mantengan consistentes.

Lista de verificación para la respuesta en la entrevista

Mencione que los índices en la pila esperan un valor mayor, luego explique i % n, las dos pasadas, el desapilado estricto, un solo apilado por índice y la complejidad amortizada.

Conclusión en una oración

Una consulta del siguiente elemento mayor en un arreglo circular se vuelve lineal con dos pasadas de índices y una pila monótona decreciente, mientras que la comparación estricta y la inicialización con -1 preservan la semántica de duplicados y valores faltantes.