数据结构考点：栈

题目描述：

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

详细解答：

解答一：一种会超时的简单算法，不用“栈”

int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize) {int *result,flag;result = (int*)malloc(sizeof(int) * temperaturesSize);returnSize = (int*)malloc(sizeof(int));*returnSize = temperaturesSize;for (int i = 0; i < temperaturesSize;i++){flag = 0;int t = temperatures[i];for (int j = 1; j <= temperaturesSize-1-i;j++){if(t<temperatures[i+j]){result[i] = j;flag = 1;break;}}if(flag==0)result[i] = 0;}return result;
}

 解法二：利用“栈”

（由于题目来源于Leetcode，所以没有主函数）

该程序以C语言为主，利用了C++的一些函数：（但是不可以再Leetcode提交）

#include<stdio.h>
#include<iostream>
#include<stack>
#include<stdc++.h>
using namespace std;
int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize) {int *result;result = (int*)malloc(sizeof(int) * temperaturesSize);memset(result, 0, sizeof(int) * temperaturesSize);*returnSize = temperaturesSize;stack<int> sta;sta.push(0);int i, j;for (i = 1;i<temperaturesSize;i++){if(temperatures[sta.top()]<temperatures[i]){while(!sta.empty()&&temperatures[sta.top()]<temperatures[i]){result[sta.top()] = i - sta.top();sta.pop();}sta.push(i);}else {sta.push(i);}}return result;
}

解法三：C++

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> result(temperatures.size(), 0);stack<int> sta;sta.push(0);int i, j;for (i = 1;i<temperatures.size();i++){if(temperatures[sta.top()]<temperatures[i]){while(!sta.empty()&&temperatures[sta.top()]<temperatures[i]){result[sta.top()] = i - sta.top();sta.pop();}sta.push(i);}else {sta.push(i);}}return result;}
};

题目来源：Leetcode739.【 739. 每日温度 - 力扣（LeetCode）】