Stock Span Problem
Você recebe o preço de fechamento de uma ação em cada dia: prices[i] é o preço no dia i. O intervalo do dia i é o número de dias consecutivos, terminando no dia i e incluindo-o, nos quais o preço foi menor ou igual a prices[i].
Retorne o intervalo de cada dia, na mesma ordem de prices. Todo intervalo é de pelo menos 1, pois um dia sempre conta a si mesmo.
Função
- pricesinteger-array
- o preço em cada dia, em ordem
- Retornainteger-array
- a extensão de cada dia, na mesma ordem
Restrições
1 ≤ prices.length ≤ 1041 ≤ prices[i] ≤ 105- Um dia anterior com o mesmo preço conta para o período; somente um preço estritamente maior o interrompe.
Exemplos
- Entrada
- prices = [31, 27, 14, 21, 30, 18, 40]
- Saída
- [1, 1, 1, 2, 4, 1, 7]
- Explicação
- O dia 3, aos 21, recua até 14 e para em 27: amplitude 2. O dia 4, aos 30, para em 31: amplitude 4. O dia 6, aos 40, supera todos os preços anteriores e abrange os 7 dias.
- Entrada
- prices = [8, 8, 3, 8]
- Saída
- [1, 2, 1, 4]
- Explicação
- Preços iguais contam, então o dia 1 a 8 cobre o dia 0 e recebe 2. O dia 3 a 8 cobre o dia 3 e os dois 8 anteriores, um período de 4.
- Entrada
- prices = [50, 40, 30, 20]
- Saída
- [1, 1, 1, 1]
- Explicação
- Todos os dias são mais baratos que o dia anterior, então nenhum intervalo se estende além do próprio dia, e cada intervalo é 1.
Para ir além
Agora, os preços chegam um de cada vez, e você deve informar cada intervalo à medida que o preço chega. Qual abordagem ainda funciona e o que ela mantém entre as chamadas?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Contar de trás para frente a partir de cada dia repete o trabalho: em 8000 dias com o mesmo preço, só o último dia percorre 8000 dias para trás. Ao voltar a partir de hoje, quais dias anteriores você pode pular de vez?
Quando o preço de hoje é pelo menos tão alto quanto o de algum dia anterior, esse dia anterior nunca poderá ser aquele que encerra um intervalo posterior: hoje está mais próximo e custa pelo menos o mesmo. Apenas os dias cujo preço é maior que o de todos os dias seguintes ainda importam, e seus preços caem do mais antigo para o mais recente.
Percorra os dias em ordem e mantenha em uma pilha, como índices, os dias anteriores que ainda importam. Antes de responder para hoje, remova da pilha todos os dias cujo preço seja menor ou igual ao de hoje. Uma pilha vazia significa que o intervalo retrocede até o dia 0; caso contrário, ele termina um dia depois do dia que ficou no topo. Então, empilhe o dia de hoje.
Solução
O intervalo de um dia termina no dia anterior mais próximo com um preço estritamente maior. Caminhar para trás para encontrá-lo custa até n passos por dia. Em vez disso, mantenha apenas os dias que ainda podem interromper um intervalo futuro: uma pilha de índices com preços estritamente decrescentes encontra todos os limites em uma única passagem.
Conte de trás para frente a partir de cada dia
Correta, mas não termina nos maiores testes
Intuição
Siga a definição. Para o dia i, volte um dia de cada vez enquanto o preço nesse dia for no máximo prices[i], contando também o dia i. O primeiro preço estritamente maior, ou o início do array, encerra a sequência.
Nenhuma caminhada reutiliza uma caminhada anterior. Com preços estáveis ou em alta, cada caminhada volta até o dia 0: n = 10^4 dias significa cerca de 5 × 10^7 passos.
Algoritmo
- Crie
span, um array com o mesmo tamanho deprices. - Para cada dia
i, defina um contador como 0 e um ponteirojcomoi. - Enquanto
j ≥ 0eprices[j] ≤ prices[i], adicione 1 ao contador e movajum dia para trás. - Armazene o contador em
span[i]. Após o último dia, retornespan.
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 spanPilha monotônica de dias mais quentes
Intuição
Chame o dia anterior mais próximo com um preço estritamente maior de bloqueador. O intervalo é today - blocker, ou today + 1 quando não há nenhum.
No primeiro exemplo, o dia 3 custa 21 e o dia 4 custa 30. Toda caminhada posterior alcança primeiro o dia 4, e qualquer preço que ultrapasse 30 também ultrapassa 21, então o dia 3 nunca mais pode bloquear. Em geral, quando chega o dia de hoje, todo candidato anterior com preço menor ou igual ao preço de hoje já foi descartado: remova-o. O dia que fica no topo é o bloqueador de hoje. Em seguida, empilhe o dia de hoje.
Os preços da pilha caem estritamente da base para o topo, então o primeiro que permanece é o preço maior mais próximo. No primeiro exemplo, o dia 4 remove os dias 3 e 1 e para no dia 0, resultando em um intervalo de 4 - 0 = 4. Cada dia é empilhado uma vez e removido no máximo uma vez, então a passagem é executada em O(n).
Algoritmo
- Crie o array
spane uma pilha vazia para os índices dos dias. - Para cada dia
today, remova índices da pilha enquanto o preço deles for menor ou igual aprices[today]. - Se a pilha estiver vazia, o período é
today + 1; caso contrário, étodaymenos o índice no topo. - Empilhe
todaye avance para o próximo dia. Retornespan.
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
Armadilhas e casos extremos
- Remover elementos ao encontrar
<em vez de<=. Em[8, 8, 3, 8], o último dia tem um intervalo de 4; parar no 8 anterior dá 2. - Usar
todayem vez detoday + 1quando a pilha está vazia. O dia 0 deve receber 1, não 0. - Remover elementos apenas uma vez por dia. No primeiro exemplo, 40 precisa eliminar os dias 5, 4 e 0. Parar após o dia 5 faz com que o dia 4 pareça ser seu bloqueador, resultando em um intervalo de 2 em vez de 7.
- Em Lua e R, os arrays começam em 1. Com índices baseados em 1, o intervalo para a pilha vazia é
today, nãotoday + 1.
Perguntas frequentes4
Qual é a complexidade temporal do problema do span de ações?
Tempo O(n) e espaço extra O(n) com a pilha monotônica, já que um dia sai da pilha no máximo uma vez. Percorrer os dias de trás para frente resulta em O(n²) quando os preços continuam subindo ou permanecem estáveis.
Deveríamos armazenar os preços ou os índices dos dias na pilha?
Índices dos dias. O intervalo é uma contagem de dias, e somente o índice do bloqueador fornece essa informação. prices[index] lê o preço para fazer a comparação.
O problema do span de ações pode ser resolvido sem uma pilha separada?
Sim. Comece em j = today - 1; enquanto j ≥ 0 e prices[j] ≤ prices[today], salte para j - span[j], pois todos os dias dentro desse intervalo têm preço no máximo igual a prices[j]. O intervalo é today - j. Os saltos chegam apenas a dias que a pilha manteria, então a passagem continua sendo O(n).
O problema do intervalo de ações é um problema de elemento maior anterior?
Sim, medido em dias: para cada dia, encontre o dia anterior mais próximo com um preço estritamente maior e informe a que distância ele está. Inverta a direção da varredura ou a comparação, e a mesma pilha fornece o próximo maior, o próximo menor ou o anterior menor.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def stockSpan(prices):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumento
prices = [31, 27, 14, 21, 30, 18, 40]
Saída Esperada
[1, 1, 1, 2, 4, 1, 7]