LeetCode每日温度

剑指 Offer II 038. 每日温度

请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

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

来源:LeetCode

利用栈来找到每个元素比其大的元素，下标差就是要等待的天数。

如果要进入栈的元素大于已经在栈里面的元素，将栈里的元素弹出，计算下标差就是该元素所求的天数；
如果要进入栈的元素小于已经在栈里面的元素，加入栈，直到最后元素遍历一遍之后，如果未弹出栈的就置为0.

例如，tem数组【30，20，50】
入栈：【0，30】，然后比较【1，20】,此时应该加入栈
接着【2，50】要入栈，进行比较，【1，20】出栈，此时天数就是两个下标之差。
由于【2，50】还是大于【0，30】，【0，30】出栈，天数是2
最后只剩下【2，50】，天数是0

这个解法比较巧妙的一点就是在栈里面的元素一定是从栈顶开始递减排列，这样每当遇到比刚进入栈要大的元素就会将相应的元素弹出，而且他们的下标之差也是它们之间距离的天数，也就是题目所求的答案。

用两个for循环解决，每次的cur就是已经入栈的值，在搜索看即将入栈的值是否有大于它的，有的话，记录到ans数组，跳出当前循环，cur取下一个元素。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] ans=new int[len];
        for(int i=0;i<len;i++){
            int cur = temperatures[i];
            if(cur<100){
                for(int j=i+1;j<len;j++){
                    if(temperatures[j]>cur){
                        ans[i]=j-i;
                        break;
                    }
                }
            }
        }
        return ans;
    }
}