Sword finger offer II 038 Daily temperature

Summary

Use stack , Traversal array , Compare whether the current number is larger than the top element . Big rule out stack processing , Until the stack is empty or the current number is less than the number at the top of the stack , Put the current number on the stack .

subject

Please according to the daily The temperature list temperatures , Rebuild a list , The output of its corresponding position is required to be ： To see a higher temperature , At least the number of days to wait . If the temperature doesn't rise after that , Please use... In this position 0 Instead of .

link ：https://leetcode.cn/problems/iIQa4I

Ideas

In fact, it is very similar to the collision of planets .

We use a stack to store the subscript of each element in the array , Start by traversing the array .

1. If the stack is empty , The stack .
2. If the stack is not empty , Compare the top of the stack with the size of the current element
   1. If the current element is large , Then subtract the current element subscript from the stack top subscript , Get the stack top element “ Number of days to wait ”. Then continue to compare the size with the elements in the stack .
   2. If the current element is small , The stack .

In this way, the element at the top of the stack is always the smallest , Once a larger value appears , Just dispose of all values smaller than him in the stack .

solution ： Monotonic stack

Code

public int[] dailyTemperatures2(int[] temperatures) {
    int[] result = new int[temperatures.length];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < temperatures.length; i++) {
        if (stack.isEmpty()) {
            stack.push(i);
            continue;
        }
        int current = temperatures[i];
        while (!stack.isEmpty() && current > temperatures[stack.peek()]) {
            int index = stack.pop();
            result[index] = i - index;
        }
        stack.push(i);
    }
    //  Deal with days when high temperatures cannot be observed 
    while (!stack.isEmpty()) {
        result[stack.pop()] = 0;
    }

    return result;
}

Execution results

Note here , Directly used Deque Instead of Stack, because Stack The efficiency of is too low ……