Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

I. Introduction to the topic

1

Link: LeetCode

2. The title

Given an array of integers that correspond to temperatures every day, return an array of answer, where answer[I] means higher temperatures will occur after the i-day. If the temperature does not rise after that point, substitute 0 at that point.

Example 1:

Input: temperatures =,74,75,71,69,72,76,73 [73] output:,1,4,2,1,1,0,0 [1]

Example 2:

(1,1,1,0) input: (30,40,50,60)

Example 3:

(1,1,0) input: (30,60,90)

Tip:

1 <= temperatures.length <= 105

30 <= temperatures[i] <= 100

Two. Concrete implementation

1. Implementation idea

According to the requirement of the subject is to return is higher than the day before the temperature of the collection, if not written down to 0, then how to compare is the focus of ontology, the idea is to use the stack, use in days as the stack elements, elements within the stack, compared with the former one element is less than directly into the stack, is greater than the comparison, finally get the result.

2. Implementation code

1) Their own way of implementation

public int[] dailyTemperatures(int[] temperatures) {
    // Use monotone stack, stack elements are compared with the elements in the stack, smaller than the direct stack, larger than the comparison
    // Note the number of days in stack memory
    Deque<Integer> deque = new ArrayDeque<>();
    int[] res = new int[temperatures.length];
    for (int i = 0; i < temperatures.length; i++) {
        while(! deque.isEmpty() && temperatures[deque.peek()] < temperatures[i]) {int idx = deque.pop();
            res[idx] = i - idx;
        }
        deque.push(i);
    }
    return res;
}
Copy the code

2) How to realize the friend

Search backwards for each temperature value to find a value higher than the current temperature. The idea is that you iterate from left to right all the numbers except for the last number, and the last number must be 0, so you don’t need to calculate it. As you iterate, every number goes to the next number until you find something larger than it, and the number of numbers is the number of numbers that you get.

Code:

3. Running result

3. Think after the question

In the ontology used in the stack as a media do much better than using the MAP, and question the idea of a friend is better, not with other media, saved the space use, feel is very stupid, have preconceived ideas on algorithm problem, is easier to suffer, or much thinking, in perspective, not how to do can do.