Stock Span Problem
Obtienes el precio de cierre de una acción cada día: prices[i] es el precio del día i. El período del día i es el número de días consecutivos, que termina en el día i y lo incluye, durante los cuales el precio fue menor o igual que prices[i].
Devuelve el período de cada día, en el mismo orden que prices. Cada período es de al menos 1, porque un día siempre se cuenta a sí mismo.
Función
- pricesinteger-array
- el precio de cada día, en orden
- Devuelveinteger-array
- el lapso de cada día, en el mismo orden
Restricciones
1 ≤ prices.length ≤ 1041 ≤ prices[i] ≤ 105- Un día anterior con el mismo precio cuenta para el intervalo; solo un precio estrictamente más alto lo detiene.
Ejemplos
- Entrada
- prices = [31, 27, 14, 21, 30, 18, 40]
- Salida
- [1, 1, 1, 2, 4, 1, 7]
- Explicación
- El día 3, en 21, retrocede hasta 14 y se detiene en 27: amplitud 2. El día 4, en 30, se detiene en 31: amplitud 4. El día 6, en 40, supera todos los precios anteriores y cubre los 7 días.
- Entrada
- prices = [8, 8, 3, 8]
- Salida
- [1, 2, 1, 4]
- Explicación
- Los precios iguales cuentan, así que el día 1 a 8 cubre el día 0 y obtiene 2. El día 3 a 8 cubre el día 3 y los dos 8 anteriores, un tramo de 4.
- Entrada
- prices = [50, 40, 30, 20]
- Salida
- [1, 1, 1, 1]
- Explicación
- Cada día es más barato que el día anterior, así que ningún intervalo se remonta más allá del día en sí y cada intervalo es 1.
Para ir más allá
Ahora los precios llegan de uno en uno, y debes informar cada intervalo a medida que llega su precio. ¿Qué enfoque sigue funcionando y qué conserva entre llamadas?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Contar hacia atrás desde cada día repite trabajo: con 8000 días al mismo precio, el último día por sí solo retrocede 8000 días. Cuando retrocedes desde hoy, ¿qué días anteriores puedes omitir para siempre?
Una vez que el precio de hoy es al menos tan alto como el de algún día anterior, ese día anterior nunca puede ser el que detenga un tramo posterior: hoy está más cerca y cuesta al menos lo mismo. Solo importan los días cuyo precio es más alto que el de todos los días posteriores, y sus precios disminuyen de los más antiguos a los más recientes.
Recorre los días en orden y mantén en una pila, como índices, los días anteriores que aún importan. Antes de responder por hoy, desapila todos los días cuyo precio sea menor o igual que el de hoy. Una pila vacía significa que el intervalo se remonta hasta el día 0; de lo contrario, se detiene un día después del día que queda en la cima. Después, apila el día de hoy.
Solución
El intervalo de un día termina en el día anterior más cercano cuyo precio sea estrictamente más alto. Retroceder para encontrarlo cuesta hasta n pasos por día. En su lugar, conserva solo los días que aún pueden detener un intervalo futuro: una pila de índices con precios estrictamente decrecientes encuentra todos los límites en una sola pasada.
Cuenta hacia atrás desde todos los días
Correcto, pero no termina con las pruebas más grandes
Intuición
Sigue la definición. Para el día i, retrocede un día a la vez mientras el precio de ese día sea como máximo prices[i], contando también el día i. El primer precio estrictamente mayor, o el inicio del array, termina el recorrido.
Ningún recorrido reutiliza uno anterior. Con precios constantes o crecientes, cada recorrido retrocede hasta el día 0: n = 10^4 días significa unos 5 × 10^7 pasos.
Algoritmo
- Crea
span, un arreglo tan largo comoprices. - Para cada día
i, establece un contador en 0 y un punterojeni. - Mientras
j ≥ 0yprices[j] ≤ prices[i], suma 1 al contador y retrocedejun día. - Guarda el contador en
span[i]. Después del último día, devuelvespan.
def stockSpan(prices):
span = []
for i in range(len(prices)):
count = 0
j = i
# Count today and every earlier day in a row that is not more expensive.
while j >= 0 and prices[j] <= prices[i]:
count += 1
j -= 1
span.append(count)
return spanPila monótona de días más altos
Intuición
Llama bloqueador al día anterior más cercano con un precio estrictamente mayor. El intervalo es today - blocker, o today + 1 cuando no hay ninguno.
En el primer ejemplo, el día 3 cuesta 21 y el día 4 cuesta 30. Todos los recorridos posteriores llegan primero al día 4, y cualquier precio que supere 30 también supera 21, así que el día 3 nunca puede volver a bloquear. En general, cuando llega el día de hoy, todos los candidatos anteriores cuyo precio es menor o igual que el de hoy ya no sirven: sácalos. El día que queda en la cima es el bloqueador de hoy. Después, inserta el día de hoy.
Los precios de la pila disminuyen estrictamente de abajo hacia arriba, así que el primero que queda es el precio mayor más cercano. En el primer ejemplo, el día 4 saca los días 3 y 1 y se detiene en el día 0, con un intervalo de 4 - 0 = 4. Cada día se inserta una vez y se saca como máximo una vez, por lo que el recorrido se ejecuta en O(n).
Algoritmo
- Crea el arreglo
spany una pila vacía para los índices de los días. - Para cada día
today, saca índices de la pila mientras su precio sea menor o igual queprices[today]. - Si la pila está vacía, el período es
today + 1; de lo contrario, estodaymenos el índice que está en la cima. - Apila
todayy pasa al día siguiente. Devuelvespan.
def stockSpan(prices):
span = [0] * len(prices)
higher = [] # indices of earlier days, prices strictly falling toward the top
for today, price in enumerate(prices):
# A day that is not more expensive than today can never stop a later span.
while higher and prices[higher[-1]] <= price:
higher.pop()
# The span reaches back to the nearest more expensive day, or to day 0.
span[today] = today - higher[-1] if higher else today + 1
higher.append(today)
return span
Errores comunes y casos límite
- Sacar elementos al encontrar
<en lugar de<=. En[8, 8, 3, 8], el último día tiene un intervalo de 4; detenerse en el 8 anterior da 2. - Escribir
todayen lugar detoday + 1cuando la pila está vacía. El día 0 debe obtener 1, no 0. - Sacar elementos solo una vez por día. En el primer ejemplo, 40 tiene que eliminar los días 5, 4 y 0. Detenerse después del día 5 hace que el día 4 parezca su bloqueador, lo que da un intervalo de 2 en lugar de 7.
- En Lua y R, los arreglos empiezan en 1. Con índices basados en 1, el intervalo con la pila vacía es
today, notoday + 1.
Preguntas frecuentes4
¿Cuál es la complejidad temporal del problema del span de acciones?
Tiempo O(n) y espacio adicional O(n) con la pila monótona, ya que cada día sale de la pila como máximo una vez. Recorrer hacia atrás desde cada día es O(n²) cuando los precios siguen subiendo o se mantienen estables.
¿La pila debe almacenar precios o índices de días?
Índices de días. El intervalo es un recuento de días, y solo el índice del bloqueador te da ese dato. prices[index] devuelve el precio para la comparación.
¿Se puede resolver el problema del período de una acción sin una pila independiente?
Sí. Empieza en j = today - 1; mientras j ≥ 0 y prices[j] ≤ prices[today], salta a j - span[j], ya que cada día dentro de ese tramo tiene un precio como máximo de prices[j]. El tramo es today - j. Los saltos solo aterrizan en días que la pila conservaría, así que el recorrido sigue siendo O(n).
¿Es el problema del rango de cotización un problema del elemento anterior mayor?
Sí, medido en días: para cada día, busca el día anterior más cercano con un precio estrictamente más alto e indica cuántos días atrás está. Invierte la dirección del recorrido o la comparación y la misma pila te da el siguiente mayor, el siguiente menor o el anterior menor.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def stockSpan(prices):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumento
prices = [31, 27, 14, 21, 30, 18, 40]
Salida Esperada
[1, 1, 1, 2, 4, 1, 7]