Monotonic stack - 739. Daily temperature

1 Title Description

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 .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/daily-temperatures

2 Title Example

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

Example 2:
Input : temperatures = [30,40,50,60]
Output : [1,1,1,0]

Example 3:
Input : temperatures = [30,60,90]
Output : [1,1,0]

3 Topic tips

1 <= temperatures.length <= 10⁵
30 <= temperatures[i] <= 100

4 Ideas

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 termperatures[i] > temperaturesLprevIndex] , 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 — Wheel 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 .


Complexity analysis
Time complexity :O(n), among n Is the length of the temperature list . Forward traverse temperature list — All over , For each subscript in the temperature list , There is at most one operation of entering and exiting the stack .
Spatial complexity :O(n), among n Is the length of the temperature list . You need to maintain a monotone stack to store the subscript in the temperature list .

5 My answer

class Solution {
    
    public int[] dailyTemperatures(int[] temperatures) {
    
        int length = temperatures.length;
        int[] ans = new int[length];
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < length; i++) {
    
            int temperature = temperatures[i];
            while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
    
                int prevIndex = stack.pop();
                ans[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }
        return ans;
    }
}