Daily Temperatures

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

A solução com pilha monótona executa em O(n) tempo e usa O(n) de espaço extra. Cada dia é empilhado uma vez e desempilhado no máximo uma vez, então o loop interno é executado no máximo n vezes ao longo de toda a passagem. Percorrer a partir de cada dia leva O(n²) tempo, cerca de 5 × 10^7 comparações para 10^4 dias sem nenhum dia mais quente.

Q: Por que a pilha armazena índices em vez de temperaturas?

A resposta para um dia é uma distância, today - day , então você precisa da posição do dia. O índice também informa qual entrada do array de respostas preencher quando o dia for removido. A temperatura está a apenas uma consulta de distância em temperatures[day] , então armazená-la também não acrescenta nada.

Q: É possível resolver Daily Temperatures sem uma pilha?

Sim. Percorra do último dia até o primeiro e, para o dia i , comece em j = i+1 . Enquanto o dia j não estiver mais quente, pule para o dia que responde por j , j + answer[j] ; se answer[j] for 0, não existe nenhum dia mais quente e o dia i também recebe 0. Os saltos pulam todos os dias que não podem ser a resposta, cada dia é pulado no máximo uma vez, e o tempo permanece O(n) , sem usar memória além do array de respostas.

MédioPilha monotônica

+10

Você recebe a temperatura de cada dia em uma sequência de dias: temperatures[i] é a temperatura no dia i. Para cada dia, conte quantos dias você precisa esperar depois dele até chegar um dia estritamente mais quente. Se nenhum dia mais quente chegar depois, a espera desse dia será 0.

Retorne um array do mesmo tamanho, em que a entrada i é o tempo de espera do 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 não houver nenhum

Restrições

1 ≤ temperatures.length ≤ 10⁴
30 ≤ temperatures[i] ≤ 100
Mais quente significa estritamente 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 tem temperatura 71 e o primeiro dia mais quente é o dia 2, com 72, então ele espera 2 dias. Os dias 3 e 4 têm temperatura 70: o segundo 70 não é mais quente, então o dia 3 espera até o dia 5, com 75, ou seja, 2 dias. Nada depois de 75 ou 68 é mais quente, então ambos recebem 0.

+13 testes ocultos ao enviar

Para ir além

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

Solução

Para um dia, a resposta é uma varredura para a frente, mas fazer uma varredura a partir de cada dia repete o mesmo trabalho e, quando os dias mais quentes são raros, cada varredura percorre o array até o fim. A solução é fazer cada dia responder aos dias anteriores, em vez de perguntar sobre os posteriores: uma pilha de índices que ainda estão aguardando, mantida ordenada por temperatura, fornece todas as respostas em uma única passagem.

Avance a partir de cada dia

Correta, mas não termina nos maiores testes

Intuição

Faça o que a questão pede. Para o dia i, verifique o dia i+1, depois i+2 e assim por diante, parando no primeiro dia cuja temperatura seja estritamente mais alta. A distância j-i é a resposta. Se chegar ao fim sem encontrar um dia assim, a resposta permanece 0.

Isso está correto porque a varredura visita os dias seguintes em ordem, então o primeiro dia mais quente que encontrar é o primeiro dia mais quente que existe. Parar exatamente ali também importa: uma varredura que continuasse registraria o último dia mais quente.

É lento quando os dias mais quentes estão muito distantes ou não existem. Se todos os 10^4 dias tiverem a mesma temperatura, nenhuma varredura para antes: o dia 0 verifica 9,999 dias, o dia 1 verifica 9,998, e o total é de cerca de n²/2 = 5 × 10^7 comparações. As varreduras também se sobrepõem: o dia 1 percorre quase exatamente o mesmo trecho que o dia 0 já percorreu e não aprende nada com ele.

Algoritmo

Crie um array de respostas com zeros, 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 encontrar 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 monótona de dias de espera

Intuição

Inverta a pergunta. Em vez de perguntar a cada dia o que vem depois dele, percorra os dias uma vez e deixe cada novo dia responder aos dias anteriores que ele supera. Mantenha em uma pilha, como índices, os dias que ainda não têm resposta. Quando o dia de hoje chegar, cada dia à espera que seja mais frio que hoje encontrou seu primeiro dia mais quente: hoje. Remova cada um deles da pilha e escreva today - day como resposta. Depois, empilhe o dia de hoje, que agora espera pelo próprio dia mais quente.

Percorra [71, 69, 72, 70, 70, 75, 68]. O dia 0 (71) é empilhado. O dia 1 (69) não é mais quente que 71, então é empilhado no topo: a pilha contém os dias [0, 1]. O dia 2 (72) remove da pilha o dia 1 (espera 1) e depois o dia 0 (espera 2), e é empilhado. Os dias 3 e 4 (70 e 70) são empilhados; o segundo 70 não remove o primeiro, porque igual não é mais quente. O dia 5 (75) remove da pilha o dia 4 (espera 1), o dia 3 (espera 2) e o dia 2 (espera 3). O dia 6 (68) é empilhado. Os dias 5 e 6 ainda estão à espera no final, então continuam com 0. A resposta é [2, 1, 3, 2, 1, 0, 0].

Por que só o topo importa: as temperaturas na pilha nunca aumentam da base para o topo. Um dia só é empilhado depois que todos os dias mais frios acima dele são removidos, então tudo que está abaixo dele é pelo menos tão quente quanto ele. Se hoje não é mais quente que o topo, também não é mais quente que nenhum dos dias abaixo dele, e você pode parar de remover. Um dia sai da pilha assim que o primeiro dia mais quente aparece, então o tempo de espera registrado é até o primeiro dia mais quente, não até o mais quente de todos.

A pilha contém índices, não temperaturas, porque a resposta é uma distância e porque você precisa saber qual posição da resposta preencher. Leia a temperatura novamente com temperatures[day]. Cada dia é empilhado uma vez e removido da pilha no máximo uma vez, então todas as remoções ao longo de todo o percurso somam no máximo n, e o tempo total é O(n), embora um dia possa remover muitos.

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, remova-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 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

O loop da pilha tem poucas linhas; os bugs se escondem na comparação e no que a pilha armazena.

Remover elementos com >= em vez de >. Um dia com a mesma temperatura não é mais quente. Em [71, 69, 72, 70, 70, 75, 68], o dia 3 espera 2 dias pelo 75, não 1 dia pelo segundo 70.
Empilhar temperaturas em vez de índices. A resposta é uma distância em dias, e você precisa do índice para calculá-la e saber qual entrada preencher.
Usar if onde você precisa de while. Um único dia quente pode responder de uma só vez por muitos dias de espera: o 75 no primeiro exemplo responde por três.
Retornar a temperatura mais quente ou o índice do dia mais quente. A saída é quantos dias você espera, j-i.
Deixar sem resposta os dias que ainda estão na pilha. A resposta deles é 0; em C, aloque a resposta com calloc ou preencha-a, 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 em vez do primeiro.

Perguntas frequentes4

Qual é a complexidade de tempo de Daily Temperatures?

A solução com pilha monótona executa em O(n) tempo e usa O(n) de espaço extra. Cada dia é empilhado uma vez e desempilhado no máximo uma vez, então o loop interno é executado no máximo n vezes ao longo de toda a passagem. Percorrer a partir de cada dia leva O(n²) tempo, cerca de 5 × 10^7 comparações para 10^4 dias sem nenhum dia mais quente.

Por que a pilha armazena índices em vez de temperaturas?

A resposta para um dia é uma distância, today - day, então você precisa da posição do dia. O índice também informa qual entrada do array de respostas preencher quando o dia for removido. A temperatura está a apenas uma consulta de distância em temperatures[day], então armazená-la também não acrescenta nada.

É possível resolver Daily Temperatures sem uma pilha?

Sim. Percorra do último dia até o primeiro e, para o dia i, comece em j = i+1. Enquanto o dia j não estiver mais quente, pule para o dia que responde por j, j + answer[j]; se answer[j] for 0, não existe nenhum dia mais quente e o dia i também recebe 0. Os saltos pulam todos os dias que não podem ser a resposta, cada dia é pulado no máximo uma vez, e o tempo permanece O(n), sem usar memória além do array de respostas.

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 armazena índices. A mesma pilha monotônica, invertida para desempilhar quando encontra um valor menor, também responde a perguntas sobre o próximo elemento menor.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

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