【算法题】11.每日气温

题目

根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

示例:

输入: [73, 74, 75, 71, 69, 72, 76, 73]
输出: [1, 1, 4, 2, 1, 1, 0, 0]

解析：

通过栈结构存储 相应的索引与温度

1. 声明一个 带索引与温度的结构体，开辟相应的栈空间，开辟返回数组并将其置为0。
2. 遍历输入信息，若为空栈，将对应信息入栈；若非空栈，比较当前温度与栈顶温度，若大于栈顶温度，则用当前索引减去栈顶索引，出栈，继续比较；若小于等于当前栈顶温度，则入栈；继续遍历。
3. 遍历完成后，释放栈空间。
4. （4.18注：可以仅生成一个数组空间，入栈索引，节省掉温度所占用的空间）。

复杂度分析：

时间复杂度：
空间复杂度：

代码

1. 方案一

       int* dailyTemperatures(int* T, int TSize, int* returnSize){
        
   
   
        int *n = (int *)calloc(TSize,sizeof(int));
        int *stack = (int *)calloc(TSize,sizeof(int));
   
        *returnSize = TSize;
   
        
        int top = - 1;
   
        int i = TSize - 1;
   
        while (i >= 0){
            int tVal = T[i];
            n[i] = 0;
            if (top == -1 )
            {
               top++;
               stack[top] = i;
               i--;
            }else if (tVal < T[stack[top]])
            {
                n[i] = stack[top] - i;
                top++;
                stack[top] = i;
                i--;
               
   
            }else if (tVal >= T[stack[top]])
            {
                
               if (top > - 1)
                {
                   top--;
   
                }else{
                   i--;
                }
            }
        }
        return n;
   }