Daily Temperatures

Q: Qual é a complexidade de tempo de Daily Temperatures?

A solução com pilha monotônica executa em O(n) de tempo e usa O(n) de espaço extra, porque cada dia é inserido uma vez e removido no máximo uma vez. Percorrer os dias seguintes a partir de cada dia leva O(n²) de tempo, cerca de 5 × 10^7 comparações para 10^4 dias sem nenhum dia mais quente.

MédioPilha monotônica

+10

temperatures[i] é a temperatura no dia i. Para cada dia, conte quantos dias você espera depois dele até chegar um dia estritamente mais quente, ou 0 se nenhum dia mais quente vier depois. Retorne um array do mesmo tamanho, em que a entrada i é o tempo de espera para o dia i.

Função

dailyTemperatures(temperatures: integer-array) → integer-array

temperaturesinteger-array: a temperatura de cada dia, em ordem
Retornainteger-array: para cada dia, o número de dias até um dia mais quente, ou 0 se nenhum chegar

Restrições

1 ≤ temperatures.length ≤ 10⁴
30 ≤ temperatures[i] ≤ 100
Mais quente significa estritamente uma temperatura mais alta: um dia posterior com a mesma temperatura não conta.

Exemplos

Entrada: temperatures = [71, 69, 72, 70, 70, 75, 68]
Saída: [2, 1, 3, 2, 1, 0, 0]
Explicação: O dia 0 (71) espera 2 dias pelo 72. O dia 3 (70) ignora o 70 igual no dia 4 e espera 2 dias pelo 75. Nada depois do 75 ou do 68 é mais quente, então ambos recebem 0.

Para ir além

As temperaturas assumem apenas 71 valores, de 30 a 100. Como uma tabela indexada pela temperatura poderia responder por todos os dias em uma única passagem da direita para a esquerda, e a que custo?

Solução

Uma varredura para a frente a partir de cada dia repete trabalho e, quando os dias quentes são raros, cada varredura vai até o fim. Em vez disso, percorra os dias uma única vez e deixe cada novo dia responder aos dias anteriores que ele supera. Os dias que ainda aguardam ficam em uma pilha cujas temperaturas nunca aumentam da base ao topo, então todas as respostas são obtidas em uma única passagem.

Avance a partir de cada dia

Correta, mas não termina nos maiores testes

Intuição

Para o dia i, verifique os dias i+1, i+2 e assim por diante, e pare no primeiro dia estritamente mais quente j. A resposta é j-i, ou 0 se a busca chegar ao fim. Percorrer em ordem faz com que o primeiro dia mais quente que você encontra seja o primeiro que existe.

Se todos os 10^4 dias tiverem a mesma temperatura, nenhuma busca para antes do fim: cerca de n²/2 = 5 × 10^7 comparações, e o dia 1 percorre quase o mesmo caminho que o dia 0 já percorreu.

Algoritmo

Crie um array de respostas preenchido com zeros, com uma entrada por dia.
Para cada dia i, percorra j de i+1 até o último dia.
No primeiro j em que temperatures[j] > temperatures[i], armazene j-i e interrompa a busca.
Retorne o array de respostas; os dias cuja busca não encontrou nada permanecem com 0.

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if temperatures[j] > temperatures[i]:
                answer[i] = j - i  # the first warmer day, so stop here
                break
    return answer

Pilha monotônica de dias de espera

Intuição

Mantenha os dias que ainda não têm resposta em uma pilha, como índices. Quando o dia de hoje chegar, retire da pilha todos os dias em espera que sejam mais frios que hoje: hoje é o primeiro dia mais quente para eles, então a resposta é today - day. Em seguida, empilhe o dia de hoje.

Só é preciso verificar o topo. Um dia só é empilhado depois que todos os dias mais frios acima dele forem retirados, então as temperaturas na pilha nunca aumentam da base para o topo. Se hoje não for mais quente que o topo, também não será mais quente que nenhum dia abaixo dele, e você para de retirar elementos. No primeiro exemplo, o dia 5 (75) retira os dias 4, 3 e 2, com esperas de 1, 2 e 3, enquanto o segundo 70 nunca retirou o primeiro, pois uma temperatura igual não é mais quente.

Cada dia é empilhado uma vez e retirado no máximo uma vez, então o total de remoções é no máximo n: tempo O(n), embora um dia possa retirar muitos elementos.

Algoritmo

Crie um array de respostas preenchido com zeros e uma pilha vazia de índices.
Para cada dia today, enquanto o dia no topo da pilha for mais frio que hoje, retire-o da pilha e defina sua resposta como today menos seu índice.
Empilhe today.
Após o loop, os dias que ainda estiverem na pilha não têm um dia mais quente e mantêm o valor 0. Retorne o array de respostas.

def dailyTemperatures(temperatures):
    answer = [0] * len(temperatures)
    waiting = []  # indices of days with no warmer day yet, colder toward the top
    for today, temp in enumerate(temperatures):
        # Today is the first warmer day for every colder day on top of the stack.
        while waiting and temperatures[waiting[-1]] < temp:
            day = waiting.pop()
            answer[day] = today - day
        waiting.append(today)
    # Days still waiting never get a warmer day and keep their 0.
    return answer

Armadilhas e casos extremos

Desempilhar usando >= em vez de >. No primeiro exemplo, o dia 3 espera 1 dia pelo segundo 70, em vez de 2 dias pelo 75.
Empilhar as temperaturas em vez dos índices. Assim, você não consegue calcular a distância nem determinar qual entrada da resposta preencher.
Usar if quando você precisa de while. Um dia quente pode responder a muitos dias de espera: 75 no primeiro exemplo responde a três.
Deixar sem valor as respostas dos dias que ainda estão na pilha. A resposta deles é 0; em C, aloque a resposta com calloc, porque a memória de malloc contém lixo.
Deixar a varredura para a frente passar do primeiro dia mais quente. Sem o break, ela registra o último dia mais quente.

Perguntas frequentes3

Qual é a complexidade de tempo de Daily Temperatures?

A solução com pilha monotônica executa em O(n) de tempo e usa O(n) de espaço extra, porque cada dia é inserido uma vez e removido no máximo uma vez. Percorrer os dias seguintes a partir de cada dia leva O(n²) de tempo, cerca de 5 × 10^7 comparações para 10^4 dias sem nenhum dia mais quente.

É possível resolver Daily Temperatures sem uma pilha?

Sim. Preencha as respostas do último dia para trás e, para o dia i, comece em j = i+1; enquanto o dia j não for mais quente, pule para j + answer[j], o dia que responde para j. Se answer[j] for 0, o dia i também recebe 0. Os saltos pulam os dias que não podem responder para i: tempo O(n), sem memória extra.

Como Daily Temperatures se relaciona com Next Greater Element?

É a mesma pergunta feita para cada posição: encontre o próximo valor maior à direita. Next Greater Element retorna esse valor; Daily Temperatures retorna a distância até ele, e é por isso que a pilha guarda índices. A mesma pilha, invertida para desempilhar ao encontrar um valor menor, responde a perguntas sobre o próximo elemento menor.

def dailyTemperatures(temperatures):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

temperatures = [71, 69, 72, 70, 70, 75, 68]

Saída Esperada

[2, 1, 3, 2, 1, 0, 0]