739.每日温度

一、题目描述

根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。

例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]

提示:气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。

二、题解

1.算法描述

  • 暴力法:循环遍历,不再赘述

2.个人分析

这道题使用栈的解法:参考江不知的评论

  1. 声明一个存放索引的辅助栈
  2. 先将T[0]压入栈中
  3. T[1]开始遍历
    1. 当辅助栈不为空时,辅助栈中的索引对应的元素小于待入栈元素时,令res[栈顶索引] = i - 栈顶索引,并出栈
    2. 否则,辅助栈中的索引对应的元素大于待入栈元素,入栈即可
  4. 当辅助栈不为空时,说明:之后都不会升高,在该位置用 0 来代替。

3.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int *dailyTemperatures(int *T, int TSize, int *returnSize)
{
int *res = (int *)malloc(TSize * sizeof(int));
int stack[TSize];
int top = -1;

int i = 0;
stack[++top] = i;
for (i = 1; i < TSize; i++)
{
while (top != -1 && T[stack[top]] < T[i])
{
res[stack[top]] = i - stack[top];
top--;
}
stack[++top] = i;
}
while (top != -1)
{
res[stack[top]] = 0;
top--;
}
*returnSize = TSize;
return res;
}

这个解法就很巧妙了,时空复杂度为O(n),比暴力法要好一点,然而我只想到了暴力法……