Leetcode739 daily temperature

Given an array of integers  temperatures , Indicates the daily temperature , Returns an array  answer , among  answer[i]  It means in the i After heaven , Will have a higher temperature . If the temperature doesn't rise after that , Please use... In this position  0 Instead of .

eg：

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

You can maintain a monotonic stack that stores subscripts , The temperature in the temperature list corresponding to the subscript from the bottom of the stack to the top of the stack decreases in turn . If a subscript is in the monotone stack , Indicates that the next higher temperature subscript has not been found .

Forward traverse temperature list . For each element in the temperature list temperatures[i], If the stack is empty , Will directly i Into the stack , If the stack is not empty , Compare stack top elements prevIndex Corresponding temperature temperatures[prevIndex] And current temperature temperatures[i], If temperatures[i] > temperatures[prevIndex], Will prevIndex remove , And will prevIndex The corresponding waiting days are assigned i - prevIndex, Repeat the above operation until the stack is empty or the temperature corresponding to the top element of the stack is less than or equal to the current temperature , And then i Into the stack .

Why can I update it when I play the stack ans[prevIndex] Well ？ Because in this case , About to enter the stack i Corresponding temperatures[i] It must be temperatures[prevIndex] The first larger element on the right , Imagine if prevIndex and i There are elements larger than it , Suppose the subscript is j, that prevIndex It must be in the subscript j The round of was bounced off .

Because the monotonic stack satisfies the corresponding temperature decrease from the bottom of the stack to the top of the stack , So every time an element is put on the stack , Will remove all elements with lower temperatures , And update the waiting days corresponding to the stack element , This ensures that the number of waiting days must be minimal .

Here is a specific example to help readers understand monotone stack . For temperature list [73,74,75,71,69,72,76,73], Monotonic stack stack The initial state of is empty , answer ans The initial state of is [0,0,0,0,0,0,0,0], Follow these steps to update the monotone stack and answer , The elements in the monotone stack are subscripts , The numbers in brackets indicate the temperature corresponding to the subscript in the temperature list .

When i=0 when , Monotone stack is empty , So it will 0 Into the stack .

stack=[0(73)]

ans=[0,0,0,0,0,0,0,0]

When i=1 when , because 74 Greater than 73, So remove the top element 0, assignment ans[0]=1−0, take 1 Into the stack .

stack=[1(74)]

ans=[1,0,0,0,0,0,0,0]

When i=2 when , because 75 Greater than 74, So remove the top element 11, assignment ans[1]=2−1, take 2 Into the stack .

stack=[2(75)]

ans=[1,1,0,0,0,0,0,0]

When i=3 when , because 71 Less than 75, So it will 3 Into the stack .

stack=[2(75),3(71)]

ans=[1,1,0,0,0,0,0,0]

When i=4 when , because 69 Less than 71, So it will 4 Into the stack .

stack=[2(75),3(71),4(69)]

ans=[1,1,0,0,0,0,0,0]

When i=5 when , because 72 Greater than 69 and 71, So remove the top elements in turn 4 and 3, assignment ans[4]=5−4 and ans[3]=5−3, take 5 Into the stack .

stack=[2(75),5(72)]

ans=[1,1,0,2,1,0,0,0]

When i=6 when , because 76 Greater than 72 and 75, So remove the top elements in turn 5 and 2, assignment ans[5]=6−5 and ans[2]=6-2, take 6 Into the stack .

stack=[6(76)]

ans=[1,1,4,2,1,1,0,0]

When i=7 when , because 73 Less than 76, So it will 7 Into the stack .

stack=[6(76),7(73)]

ans=[1,1,4,2,1,1,0,0]

Code implementation

public int[] dailyTemperatures(int[] t) {
    int[] res = new int[t.length];
    Stack<Integer> s = new Stack<>();
    for(int i = 0 ; i < t.length;i++){
        while(!s.isEmpty() && t[i] > t[s.peek()]){
            int index = s.pop();
            res[index] = i - index;
        }
        s.push(i);
    }
    return res;

}