70.每日温度（单调栈）

1.题目描述

给定一个整数数组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]

2.思路及模拟图解

3.代码

/** * Note: The returned array must be malloced, assume caller calls free(). */ int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize) { int st[temperaturesSize]; int top = 0; int* res = (int*)malloc(temperaturesSize * 4); for (int i = 0; i < temperaturesSize; i++) { res[i] = 1; // 初始化，避免随机值 } for(int i=0;i<temperaturesSize;i++){ while(top!=0 && temperatures[i]>temperatures[st[top-1]]){ int index = st[top-1]; res[index] = i-index; top--; } st[top] = i; top++; } *returnSize = temperaturesSize; while(top!=0){//栈没有空，表示找不到大于它的就置为0 res[st[top-1]] = 0; top--; } return res; }