一、题目粗心
标签: 栈和队列
https://leetcode.cn/problems/daily-temperatures
给定一个整数数组 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
二、解题思路
什么是枯燥栈？枯燥栈通过维持栈内值的枯燥递增（递加）性，在整体 O(n) 的工夫内解决须要大小比拟的问题。
思路：能够维持一个枯燥递加的栈，示意每天的温度，为了不便计算天数差，这里寄存地位（即日期）而非温度自身。从左向右遍历温度数组，对于每个日期 p，如果 p 的温度比栈顶存储地位 q 的温度高，则咱们取出 q，并记录 q 须要期待的天数 p -q；反复这一过程，直到 p 的温度小于等于栈顶地位的温度或空栈时，咱们将 p 插入栈顶，而后思考下一天。在这个过程中栈内数组永远放弃枯燥递加，防止了应用排序进行比拟。最初若栈内残余一些日期，则阐明它们之后都没有呈现更温暖的日期。
三、解题办法
3.1 Java 实现
public class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] ans = new int[temperatures.length];
Stack<Integer> 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;
}
}四、总结小记
- 2022/8/10 下雨、下雪本是很好玩的事，大了之后也不尽然，出行、生产、工作都会受到影响