739. Daily Temperatures(M)

https://leetcode.com/problems/daily-temperatures/

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

Constraints:

• 1 <= temperatures.length <= 105

• 30 <= temperatures[i] <= 100

Solution:

比如说给你输入 T = [73,74,75,71,69,76]，你返回 [1,1,3,2,1,0]。

解释：第一天 73 华氏度，第二天 74 华氏度，比 73 大，所以对于第一天，只要等一天就能等到一个更暖和的气温，后面的同理。

这个问题本质上也是找 Next Greater Number，只不过现在不是问你 Next Greater Number 是多少，而是问你当前距离 Next Greater Number 的距离而已。

相同的思路，直接调用单调栈的算法模板，稍作改动就可以，直接上代码吧：

vector<int> dailyTemperatures(vector<int>& T) {
    vector<int> res(T.size());
    // 这里放元素索引，而不是元素
    stack<int> s; 
    /* 单调栈模板 */
    for (int i = T.size() - 1; i >= 0; i--) {
        while (!s.empty() && T[s.top()] <= T[i]) {
            s.pop();
        }
        // 得到索引间距
        res[i] = s.empty() ? 0 : (s.top() - i); 
        // 将索引入栈，而不是元素
        s.push(i); 
    }
    return res;
}

JAVA Version:
class Solution {
    public int[] dailyTemperatures(int[] temperatures) 
    {
        int[] days = new int[temperatures.length];
        Stack<Integer> stack = new Stack<Integer>();
        for(int i = temperatures.length-1; i>=0; i--)
        {
            while(!stack.empty() && temperatures[stack.peek()] <= temperatures[i])
            {
                stack.pop();
            }
            days[i] = stack.empty() ? 0 : (stack.peek()-i);
            stack.push(i);
        }
        return days;
    }
}