1. Title Description

Generate a new list based on the daily temperature list. The output of the corresponding position is: the minimum number of days to wait for higher temperatures to be observed. If the temperature does not rise after that point, substitute 0 at that point.

For example, given a list of temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output would be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length range of the temperature list is [1, 30000]. Each temperature is an integer in the [30, 100] range of degrees Fahrenheit.

Second, train of thought analysis

Violent solution

When I saw this question, the first thing that came to my mind was the direct violence solution:

const dailyTemperatures = function(T) {
    let len = T.length
    for(let i = 0; i < len; i++){
    let index = i + 1
    while(index < len && T[index] <= T[i]){
        index++
    }
    T[i] = index >= len ? 0 : index - i
    }
    return T
};
Copy the code

But after writing the code, an array is traversed by two layers, and the time complexity of this violent solution goes straight up to O(n^2), which is obviously not satisfactory to the interviewer in the interview.

So we have to figure out how to optimize it.

Use stacks to avoid repeated operations

We actually do a lot of repetitive work in the cycle of violence.

[73, 74, 75, 71, 69, 72, 76, 73]
Copy the code

Take 75, for example. In our search for the first temperature higher than 75, we passed 71, 69, 72, 76, where 72 is the target temperature of 71.

When the outer circle reaches 71, we repeat the path we just walked: 69, 72.

We need to find ways to reduce this duplication: using the stack structure can avoid duplication.

Try to maintain a decrement stack:

  • Traverses the temperature, and pushes the index into the stack when it is monotonically decreasing;
  • When a temperature is about to break the monotonically decreasing trend (higher than the previous temperature value), the top of the stack is indexed out of the stack. The difference in the index between the two temperatures is the number of days the previous temperature has to wait.

In this process, the entire array is traversed only once, with only a few operations on and off the stack, so the time complexity is O(n).

AC code

** * @param {number[]} T * @return {number[]} * const dailyTemperatures = function(T) {const len = Const stack = [] // initializing stack const res = (new Array(len)).fill(0) // Initializing result Array defaults to 0 for(let I =0; i<len; I++) {// if stack is not empty, While (stack.length && T[I] > T[stack[stack.leng-1]]) {const top = stack.pop() // Index the corresponding temperature on the stack The index difference between the current temperature at the top of the stack and the temperature to break the decline trend (the first temperature higher than it) is the number of days to wait res[top] = i-top} // the index of the temperature to be pushed, Stack. Push (I)} // return result array return res};Copy the code

Four,

  • Violence traversal must be optimized;
  • The stack structure helps us avoid repeated operations;
  • Remove unnecessary data from the stack in a timely manner.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign