739. Daily temperature

LeetCode leetcode-cn.com/problems/da…

The title

According to the daily temperature list, please generate a new list. The output of the corresponding position is how many more days need to wait for the temperature to rise beyond that day. If it does not rise after that, replace it with 0 at that position.

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.

Their thinking

Idea: monotonous stack

For each element, go to the right and find the first element larger than it, and calculate the distance between them.

So using the brute force solution, the code looks like this:

def dailyTemperatures(self, T: List[int]) -> List[int]:
    length = len(T)

    ans = [0] * length

    for i in range(length):
        for j in range(i+1, length):
            if T[i] < T[j]:
                ans[i] = j - i
                break

    return ans
Copy the code

In this case, execution times out.

We need to optimize, use stacks, trade space for time.

As can be seen from the previous violent solution, the main concern for solving the problem is the size of the element on the right.

Let’s look at the main problem of the violent solution. When you go through a set of numbers, looking for the next element that’s bigger than the current element, you’re doing a lot of repeated queries.

The solution is to use the stack to store the elements on the right for subsequent comparison, and to strip out elements that do not need to be compared repeatedly.

Now let’s think about iterating from the right, what do we want to eliminate?

When traversing from right to left, we want to keep the larger elements on the stack.

  • When the stack is empty, the current element is pushed onto the stack.
  • When traversing, if the current element is larger than the top element, it is considered to remove the element from the stack until the top element is larger than the current element.
  • In this case, the element at the top of the stack is actually the first larger element to the right of the current element. The distance is calculated, and then the current element is added to the stack and the loop continues
  • Repeat the above steps until the traversal is complete.

The specific code is as follows.

Code implementation

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        length = len(T)

        ans = [0] * length

        This is implemented with a list
        The last element of the list is the top element of the stack
        stack = []

        Start traversing from right to left
        for i in range(length - 1.- 1.- 1) :Unstack if the current element is greater than or equal to the top element of the stack
            Until the current element is less than the top of the stack
            while stack and T[i] >= T[stack[- 1]]:
                stack.pop()
            
            The top element of the stack is the first larger element to the right of the current element
            if stack and T[i] < T[stack[- 1]]:
                ans[i] = stack[- 1] - i

            If the stack is empty, push the current element onto the stack
            stack.append(i)

        return ans
Copy the code

Achieve results

conclusion

  • So just to clarify the problem, they’re asking each element to go to the right and find the first element larger than it, and calculate the distance between them.
  • Use brute force solutions to try to solve the problem first (Python writing timeout), but you can see that some of the queries are duplicate. Try using space for time optimization.
  • With the help of the stack, traverse from right to left. Maintain elements in the stack to avoid repeated queries. Specific approach (traversal from right to left) :
    • When the stack is empty, the element is pushed;
    • Traversal, when the current element is greater than or equal to the top element of the stack, the stack is removed until the current element is smaller than the top element of the stack.
    • The top element is actually the first larger element to the right of the current element, calculates the distance between the two, and pushes the current element onto the stack. For the next onei-1Index elements for comparison. (In this case, the previous element can be culled because the element smaller than the current T[I] cannot be the first element to the right of T[i-1].)
    • Continue traversing until the end.

The article is original, if you think it can be written, welcome to pay attention to. Wechat public account “Shusuoji Lu” synchronous update, also welcome to follow.