739.每日温度

发表于 | 分类于
字数统计: 426 | 阅读时长 ≈ 1

一、题目描述

根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 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)，比暴力法要好一点，然而我只想到了暴力法……