Today’s topic comes from LeetCode Question No. 739: Daily temperature.

Topic describes

From the daily temperature list, please generate a new list with the corresponding input for how many more days you 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.

title

One of the most “difficult” points of this topic is the understanding of the topic.

Temperatures given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], why is the output [1, 1, 4, 2, 1, 0, 0]?

Let’s explain them one by one.

For 73, it takes one day for the temperature to go up, so by the next day, the temperature goes up to 74, so it’s one.

For input 74, it takes one day for the temperature to rise, so on the third day, the temperature rises to 75, so the corresponding result is one.

For 75, after one day it finds that the temperature is 71, it doesn’t go beyond that, it waits, it waits for four days, and on the seventh day it waits for the temperature to go up, and it goes up to 76, so the corresponding result is 4.

For 71, after one day, it finds that the temperature is 69, it doesn’t go beyond that, it waits, it waits for two days, and on the sixth day, it waits for an increase in temperature, and the temperature rises to 72, so the corresponding result is 2.

For the input 69, it finds after a day that the temperature is 72, which has exceeded it, so the corresponding result is 1.

For input 72, it goes through a day and finds that the temperature is 76, which has exceeded it, so the corresponding result is 1.

For input 76, no subsequent temperature can exceed it, so the corresponding result is 0.

For input 73, no subsequent temperature can exceed it, so the corresponding result is 0.

Ok, so now that we understand the problem let’s think about how to solve it.

The first idea is to search backwards for each temperature value and find a value higher than the current temperature, which is the easiest way to think about it.

And the idea is that you go from left to right and you go through everything except the last number, and the last number is going to be 0, so you don’t have to compute it.

As you traverse, each number goes to the next number until you find something larger than it, and the number of numbers is the corresponding output value.

The code is as follows:

public int[] dailyTemperatures(int[] T) {
    int length = T.length;
    int[] result = new int[length];
    for (int i = 0; i < length; i++) {
        int current = T[i];
        if (current < 100) {
            for (int j = i + 1; j < length; j++) {
                if (T[j] > current) {
                    result[i] = j - i;
                    break; }}}}return result;
}
Copy the code

The label for this problem is stack, so let’s think about how we can solve it with a stack.

But this stack is a bit special. It’s a decrement stack: there are only decrement elements in the stack.

Specific operations are as follows:

Traverse the entire array, if the stack is not empty, and the current number is greater than the stack elements, so it’s not decreasing stack if directly into the stack, so you need to remove the stack elements, because the current number is greater than the stack elements number, and must be the first element is greater than the stack, the distance of subscript difference is both directly.

Continue to look at the new top of the stack until the current number is less than or equal to the top of the stack and stop, and then push the number onto the stack. This way you can keep decreasing the stack and calculate the distance between each number and the first number greater than it.

Animation understand

Video animation understanding link address

Complexity analysis

This method only needs to traverse the array once, each element is pushed and popped on the stack at most once, and the algorithm complexity is O(n).

Code implementation

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res(n, 0);
        stack<int> st;
        for (int i = 0; i < temperatures.size(); ++i) {
            while(! st.empty() && temperatures[i] > temperatures[st.top()]) {auto t = st.top(); st.pop();
                res[t] = i - t;
            }
            st.push(i);
        }
        returnres; }};Copy the code

Related topics

Using the stack, you can also solve the following common problems:

  • Results of solving arithmetic expressions (LeetCode 224, 227, 772, 770)
  • Solve for the largest rectangular region in the histogram (LeetCode 84)