LeetCode[中等] 739. 每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
思路 栈
暴力法为遍历列表中的每个元素。
遍历每日温度，若当日温度大于栈顶温度，说明当日是栈顶元素的升温日，因此将栈顶元素出栈，计算其与当日的天数差，存放于结果数组中。
public class Solution {
public int[] DailyTemperatures(int[] temperatures) {
Stack<int> stack = new Stack<int>();
int[] answer = new int[temperatures.Length];
for(int i = 0; i < temperatures.Length; i++)
{
//int temperature = temperatures[i];
while(stack.Count > 0 && temperatures[i] > temperatures[stack.Peek()])//当日为升温日
{
int peek = stack.Pop();//温度低于升温日温度 出栈
answer[peek] = i - peek;//升温日索引 - 栈顶索引
}
stack.Push(i);//不是升温日则出栈
}
return answer;
}
}复杂度分析
- 时间复杂度：O(n)，其中 n 是数组 temperatures 的长度。需要从左到右遍历数组 temperatures 计算结果数组 answer 的值，由于每个下标最多入栈和出栈各一次，结果数组 answer 中的每个元素的计算时间是 O(1)，因此时间复杂度是 O(n)。
- 空间复杂度：O(n)，其中 n 是数组 temperatures 的长度。空间复杂度主要取决于栈空间，栈内元素个数不会超过 n。