当前位置：网站首页>leetcode 739. Daily Temperatures Daily Temperatures (Moderate)

leetcode 739. Daily Temperatures Daily Temperatures (Moderate)

2022-08-10 13:53:00 【InfoQ】

I. The main idea of the title

tag: stack and queue

https://leetcode.cn/problems/daily-temperatures

Given an array of integers temperatures representing the temperature of each day, returns an array answer where answer[i] refers to the nextHigher temperatures appeared a few days later.If the temperature doesn't rise after that, use 0 instead in that location.

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]

Tips:

1 <= temperatures.length <= 105

30 <= temperatures[i] <= 100

Second, problem solving ideas

What is a monotonic stack?Monotonic stacks handle problems requiring size comparisons in overall O(n) time by maintaining monotonically increasing (decreasing) properties of the values in the stack.

Idea: A monotonically decreasing stack can be maintained to represent the daily temperature. In order to facilitate the calculation of the difference in days, the storage location (that is, the date) instead of the temperature itself.Traverse the temperature array from left to right. For each date p, if the temperature of p is higher than the temperature of the storage location q at the top of the stack, we take out q and record the number of days p-q that q needs to wait for; repeat this process until the value of pWhen the temperature is less than or equal to the temperature at the top of the stack or when the stack is empty, we insert p at the top of the stack and consider the next day.In this process, the array on the stack is always monotonically decreasing, avoiding the use of sorting for comparison.If there are some dates left in the stack at the end, it means that none of them are followed by a warmer date.

Three, problem solving method

3.1 Java implementation

public class Solution {
 public int[] dailyTemperatures(int[] temperatures) {
 int[] ans = new int[temperatures.length];
 Stack desStack = new Stack<>();
 for (int i = 0; i < temperatures.length;i++) {
 while (!desStack.isEmpty()) {
 int preIndex = desStack.peek();
 if (temperatures[i] <= temperatures[preIndex]) {
 break;
 }
 desStack.pop();
 ans[preIndex] = i - preIndex;
 }
 desStack.push(i);
 }
 return ans;
 }
}