【Hot100】739. Daily temperature

739. Daily temperature
Given an array of integers temperatures , Indicates the daily temperature , Returns an array answer , among answer[i] Refers to the i God , The next higher temperature appears in a few days . If the temperature doesn't rise after that , Please use... In this position 0 Instead of .

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

Topic understanding ：
For input 73, It needs to After a day Until the temperature rises , That is, the next day , The temperature rises to 74 , So the corresponding result is 1.

For input 74, It needs to the One day Until the temperature rises , On the third day , The temperature rises to 75 , So the corresponding result is 1.

For input 75, It passes by 1 The temperature was found to be 71, No more than it , Keep waiting , always Wait four days , Wait until the temperature rises on the seventh day , The temperature rises to 76 , So the corresponding result is 4 .

For input 71, It passes by 1 The temperature was found to be 69, No more than it , Keep waiting , always Waited two days. , Wait until the temperature rises on the sixth day , The temperature rises to 72 , So the corresponding result is 2 .

For input 69, it After a day It turns out that the temperature is 72, It's over it , So the corresponding result is 1 .

For input 72, it After a day It turns out that the temperature is 76, It's over it , So the corresponding result is 1 .

For input 76, follow-up There is no temperature Can surpass it , So the corresponding result is 0 .

For input 73, follow-up There is no temperature Can surpass it , So the corresponding result is 0 .

idea ： For each temperature value Search backward in turn , Find a value higher than the current temperature , This is the easiest way to think about it .

principle ： From left to right, all numbers except the last one are traversed once , The result of the last data must be 0, There is no need to calculate .

When traversing , Every number goes backward , Until we find a larger number , Count frequency Is the corresponding output value .

class Solution {
    
    public int[] dailyTemperatures(int[] temperatures) {
    
        int len = temperatures.length;
        int[] res = new int[len];
        for(int i=0;i<len;i++){
    
            int cur = temperatures[i];
            if(cur < 100){
    
                for(int j=i+1;j<len;j++){
    
                    if(temperatures[j] > cur){
    
                        res[i] = j-i;
                        break;
                    }
                }
            }
        }
        return res;

    }

}

Use the stack to solve ：
Decrement stack ： There are only diminishing elements in the stack .
Traverse the entire array , If the stack is not empty , And the current number is greater than the stack top element , So if you go directly to the stack, it's not Decrement stack , So you need to take out the top element of the stack , Because the current number is larger than the number of the top element of the stack , And it must be the first one greater than the number of elements at the top of the stack , Directly find out the subscript difference is the distance between the two .

Keep looking at the new stack top elements , Until the current number is less than or equal to the top element of the stack , Then put the numbers on the stack , This keeps the decrement stack going , And the distance between each number and the first number greater than it can also be calculated .

class Solution {
    
    public int[] dailyTemperatures(int[] T) {
    
        Stack<Integer> stack = new Stack<>();
        int length = T.length;
        int[] result = new int[length];

        for (int i = 0; i < length; i++) {
    
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
    
                int pre = stack.pop();
                result[pre] = i - pre;
            }
            stack.add(i);

        }
        return result;
    }

   
}