Lo que evalúa el entrevistador
Dado un arreglo de enteros que puede contener duplicados, modifícalo in situ para obtener la siguiente permutación lexicográfica estrictamente mayor; si el orden actual es el máximo, genera la permutación ascendente más pequeña.
Restricciones y casos límite
- Utiliza espacio adicional O(1) y únicamente intercambios o inversiones.
- Los valores duplicados no son identidades distintas, pero las comparaciones son numéricas.
- Los arreglos vacíos y de un solo elemento permanecen sin cambios.
- El resultado debe ser la permutación lexicográfica globalmente adyacente, no un intercambio local arbitrario.
Encontrar el pivote más a la derecha
Recorre desde la derecha buscando el primer índice i donde el valor de la izquierda sea estrictamente menor que el valor de la derecha. El sufijo ya es no creciente. Si no existe ningún pivote, todo el arreglo es el máximo; inviértelo para obtener la permutación mínima.
Intercambiar y minimizar el sufijo
Con un pivote, recorre desde la derecha buscando el primer valor mayor que nums[i]. Dado que el sufijo es no creciente, ese primer candidato es el valor mayor más pequeño posible. Intercámbialo con el pivote y luego invierte el sufijo después de i para hacerlo ascendente.
Estructura de respuesta en 30 segundos
“Recorre desde la derecha buscando el primer pivote ascendente i. Si no existe ninguno, invierte el arreglo descendente máximo. De lo contrario, encuentra el valor más a la derecha mayor que nums[i], intercámbialos e invierte el sufijo. El sufijo comienza ordenado en la dirección opuesta, por lo que esto genera el menor incremento posible en tiempo O(n) y espacio O(1).”
Preguntas de aclaración antes de responder
- ¿La modificación debe realizarse in situ? El espacio adicional permitiría ordenar una copia, mientras que in situ requiere inversión.
- ¿El orden lexicográfico es numérico o basado en cadenas? Los valores negativos y de múltiples dígitos difieren.
- ¿Los valores pueden repetirse? Los duplicados requieren comparaciones estrictas tanto para el pivote como para el candidato de intercambio.
Análisis paso a paso
Para [1,2,3], el pivote en 1 se intercambia con el valor mayor más pequeño del sufijo 2, dejando [2,1,3] tras la inversión del sufijo. Para [3,2,1], no existe ningún pivote, por lo que la inversión produce [1,2,3].
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
j = n - 1
while nums[j] <= nums[i]:
j -= 1
swap(nums[i], nums[j])
reverse(nums, i + 1, n - 1)Usa “mayor o igual que” al omitir candidatos de pivote y “menor o igual que” al omitir candidatos de intercambio, asegurando un incremento estricto. Invierte en lugar de ordenar porque el sufijo ya está ordenado, de modo que la inversión se mantiene lineal e in situ.
Respuesta modelo de alta calidad
“La siguiente permutación cambia la posición más a la derecha posible y hace que todo lo que esté después sea lo más pequeño posible. Encuentro el pivote más a la derecha donde el valor de la izquierda es estrictamente menor que el valor de la derecha, lo intercambio con el valor más a la derecha mayor que él e invierto el sufijo. Si no hay pivote, significa que el arreglo es el máximo, por lo que invierto todo el arreglo. Los recorridos y la inversión son O(n) y el algoritmo utiliza variables adicionales constantes.”
Errores comunes
- Encontrar el pivote desde la izquierda y cambiar una posición de mayor orden.
- Detenerse después del intercambio sin minimizar el sufijo.
- Usar mayor o igual que para el candidato de intercambio, de modo que los duplicados no logren incrementarse estrictamente.
- Llamar a un ordenamiento general en el sufijo y violar la restricción in situ.
- Retornar un arreglo descendente sin cambios cuando debería volver al orden mínimo.
Síntomas de fallo y soluciones
Si [1,3,2] se convierte en [3,1,2], el pivote está demasiado a la izquierda; el resultado correcto es [2,1,3]. Si [1,1,5] intercambia valores iguales, el límite de comparación estricta es incorrecto.
Implementación en producción
Acepta una secuencia mutable de acceso aleatorio e inviértela con dos punteros. Si la comparación puede desbordarse o el orden del lenguaje difiere, define el comparador y la política para entradas inválidas en el límite de la interfaz.
Lista de verificación de validación
Prueba con arreglos vacíos, de un solo elemento, ascendentes, descendentes, con duplicados, con un pivote al final y con múltiples óptimos iguales. Para arreglos pequeños, genera todas las permutaciones distintas, ordénalas lexicográficamente y verifica que la función retorne el siguiente elemento o vuelva al primero.
Preguntas de seguimiento y respuestas
¿Por qué el pivote debe ser el que está más a la derecha?
Un pivote situado más a la derecha cambia una posición de menor orden. Elegir el valor mayor más pequeño posible y minimizar su sufijo produce, por lo tanto, la permutación adyacente en lugar de saltarse órdenes válidos.
¿Por qué se puede invertir el sufijo directamente?
El recorrido de derecha a izquierda del pivote demuestra que el sufijo es no creciente. Tras el intercambio, invertirlo restaura el orden ascendente más pequeño sin necesidad de un ordenamiento general.
¿Qué ocurre con la k-ésima permutación siguiente?
Repetir la operación cuesta O(k n). Para un k grande, los enfoques de rank/unrank o de conteo pueden saltar directamente, pero requieren conteo combinatorio y manejo de duplicados.
Rúbrica de evaluación
- Pivote: encuentra el ascenso estricto más a la derecha.
- Intercambio: elige el primer valor estrictamente mayor desde la derecha.
- Sufijo: lo invierte para obtener el orden ascendente más pequeño.
- Casos límite: cubre arreglos descendentes, duplicados, vacíos y de un solo elemento.
- Complejidad: ofrece tiempo O(n) y espacio adicional O(1).
Comprobación de cumplimiento
Confirma que los tres pasos, los ejemplos de casos límite y la afirmación de complejidad se mantengan coherentes.
Lista de verificación de la respuesta en la entrevista
Explica el cambio más pequeño en el lado derecho, escribe el pivote, el intercambio y la inversión, usa un ejemplo con duplicados para las comparaciones estrictas y, a continuación, indica la complejidad y la prueba exhaustiva con permutaciones pequeñas.
Conclusión en una sola frase
La siguiente permutación se encuentra in situ mediante el pivote más a la derecha, el intercambio mayor más pequeño posible y una inversión del sufijo en tiempo lineal.