The title

link

Analysis of the

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.

1, the simplest way is to solve by force, go through each element, and then look for something larger than the current element. After finding it, record the difference between their positions, and then stop the inner loop. If no element is found, it defaults to 0.



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

2. After all, brute force solution is not very efficient, we can also solve it by using only the stack, which holds the index of the array elements. Let’s draw a picture













The following code

    public int[] dailyTemperatures(int[] T) {
        Stack<Integer> stack = new Stack<>();
        int[] ret = new int[T.length];
        for (int i = 0; i < T.length; i++) {
            while(! stack.isEmpty() && T[i] > T[stack.peek()]) {int idx = stack.pop();
                ret[idx] = i - idx;
            }
            stack.push(i);
        }
        return ret;
    }
Copy the code

3. We can also change the stack to an array

    public int[] dailyTemperatures(int[] T) {
        int[] stack = new int[T.length];
        int top = -1;
        int[] res = new int[T.length];
        for (int i = 0; i < T.length; i++) {
            while (top >= 0 && T[i] > T[stack[top]]) {
                int idx = stack[top--];
                res[idx] = i - idx;
            }
            stack[++top] = i;
        }
        return res;
    }
Copy the code

4, we can also refer to the number84. Largest rectangle in a bar chart

Let’s look at the code

    public int[] dailyTemperatures(int[] T) {
        int length = T.length;
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[length];
        for (int i = 0; i < length; i++) {
            int h = T[i];
            if (stack.isEmpty() || h <= T[stack.peek()]) {
                stack.push(i);
            } else {
                inttop = stack.pop(); res[top] = i - top; i--; }}return res;
    }
Copy the code

5, the last solution, this is more powerful, start from the back, more efficient, beat 100% of the users, there are comments in the code, you see

    public int[] dailyTemperatures(int[] T) {
        int[] res = new int[T.length];
        // Start from the back
        for (int i = res.length - 1; i >= 0; i--) {
            int j = i + 1;
            while (j < res.length) {
                if (T[j] > T[i]) {
                    // If found, stop the while loop
                    res[i] = j - i;
                    break;
                } else if (res[j] == 0) {
                    // If not found and res[j]==0. So there's nothing after the JTH element
                    // The value greater than the JTH element, since this step is the ith element greater than the JTH element,
                    // Then obviously there is no value greater than the ith element. Terminate the while loop directly.
                    break;
                } else {
                    // If not found, and res[j]! =0 means that the JTH element is followed by something larger than the JTH element,
                    // Then we move j backwards by res[j] to find that value and compare it with the ith elementj += res[j]; }}}return res;
    }
          // Then we move j backwards by res[j] to find that value and compare it with the ith elementj += res[j]; }}}return res;
    }
Copy the code