LeetCode_单调栈_中等_739.每日温度

末蓝、 2023-10-06 22:47 41阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 **answer\[i\] 是指在第 i 天之后，才会有更高的温度**。如果气温在这之后都不会升高，请在该位置用 0 来代替。

**示例 1：**  
输入: temperatures = \[73,74,75,71,69,72,76,73\]  
输出: \[1,1,4,2,1,1,0,0\]

**示例 2：**  
输入: temperatures = \[30,40,50,60\]  
输出: \[1,1,1,0\]

**示例 3：**  
输入: temperatures = \[30,60,90\]  
输出: \[1,1,0\]

**提示：**  
1 <= temperatures.length <= 105  
30 <= temperatures\[i\] <= 100

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/daily-temperatures

## 2.思路 ##

（1）暴力穷举法  
暴力穷举法是一种比较容易想到的方法，即**使用 2 层 for 循环来求出每一天后面第一次温度高于当天的日期，然后将天数之差的结果存储到数组 answer 中即可。**

（2）单调栈

相关题目：  
[LeetCode\_单调栈\_中等\_1019.链表中的下一个更大节点][LeetCode_1019.]

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public int[] dailyTemperatures(int[] temperatures) {
        
            int n = temperatures.length;
            int[] answer = new int[n];
            for (int i = 0; i < n; i++) {
        
                for (int j = i + 1; j < n; j++) {
        
                    if (temperatures[j] > temperatures[i]) {
        
                        answer[i] = j - i;
                        break;
                    }
                }
            }
            return answer;
        }
    }

//思路2————单调栈
    class Solution {
        
    	public int[] dailyTemperatures(int[] temperatures) {
        
    	    int length = temperatures.length;
    	    int[] answer = new int[length];
    	    Deque<Integer> descStack = new ArrayDeque<>();
    	    for (int i = 0; i < length; i++) {
        
    	    	/*
    	    		temperatures[descStack.peek()] < temperatures[i]: 说明第 i 天的温度高于第 j 天 (j < i，
    	    		且 j = descStack.peek()) 的温度，那么此时第 j 天下一个更高温度出现在 i - j 天之后
    			*/
    	        while (!descStack.isEmpty() && temperatures[descStack.peek()] < temperatures[i]) {
        
    	            answer[descStack.peek()] = i - descStack.peek();
                    descStack.pop();
    	        }
    	        descStack.push(i);
    	    }
    	    return answer;
    	}
    }

[LeetCode_1019.]: https://blog.csdn.net/weixin_43004044/article/details/130052110