Leetcode739 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

eg：

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

可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。

正向遍历温度列表。对于温度列表中的每个元素 temperatures[i]，如果栈为空，则直接将 i 进栈，如果栈不为空，则比较栈顶元素 prevIndex 对应的温度 temperatures[prevIndex] 和当前温度 temperatures[i]，如果 temperatures[i] > temperatures[prevIndex]，则将 prevIndex 移除，并将 prevIndex 对应的等待天数赋为 i - prevIndex，重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将 i 进栈。

为什么可以在弹栈的时候更新 ans[prevIndex] 呢？因为在这种情况下，即将进栈的 i 对应的 temperatures[i] 一定是 temperatures[prevIndex] 右边第一个比它大的元素，试想如果 prevIndex 和 i 有比它大的元素，假设下标为 j，那么 prevIndex 一定会在下标 j 的那一轮被弹掉。

由于单调栈满足从栈底到栈顶元素对应的温度递减，因此每次有元素进栈时，会将温度更低的元素全部移除，并更新出栈元素对应的等待天数，这样可以确保等待天数一定是最小的。

以下用一个具体的例子帮助读者理解单调栈。对于温度列表 [73,74,75,71,69,72,76,73]，单调栈 stack 的初始状态为空，答案 ans 的初始状态是 [0,0,0,0,0,0,0,0]，按照以下步骤更新单调栈和答案，其中单调栈内的元素都是下标，括号内的数字表示下标在温度列表中对应的温度。

当 i=0时，单调栈为空，因此将0进栈。

stack=[0(73)]

ans=[0,0,0,0,0,0,0,0]

当 i=1时，由于 74大于 73，因此移除栈顶元素0，赋值ans[0]=1−0，将 1进栈。

stack=[1(74)]

ans=[1,0,0,0,0,0,0,0]

当 i=2时，由于 75大于74，因此移除栈顶元素11，赋值ans[1]=2−1，将2进栈。

stack=[2(75)]

ans=[1,1,0,0,0,0,0,0]

当 i=3时，由于71小于75，因此将3进栈。

stack=[2(75),3(71)]

ans=[1,1,0,0,0,0,0,0]

当 i=4时，由于69小于71，因此将4进栈。

stack=[2(75),3(71),4(69)]

ans=[1,1,0,0,0,0,0,0]

当i=5时，由于72大于69和71，因此依次移除栈顶元素4和3，赋值ans[4]=5−4 和ans[3]=5−3，将 5进栈。

stack=[2(75),5(72)]

ans=[1,1,0,2,1,0,0,0]

当 i=6时，由于76大于72和75，因此依次移除栈顶元素5和2，赋值 ans[5]=6−5 和 ans[2]=6-2，将 6进栈。

stack=[6(76)]

ans=[1,1,4,2,1,1,0,0]

当 i=7时，由于73小于76，因此将7进栈。

stack=[6(76),7(73)]

ans=[1,1,4,2,1,1,0,0]

代码实现

public int[] dailyTemperatures(int[] t) {
    int[] res = new int[t.length];
    Stack<Integer> s = new Stack<>();
    for(int i = 0 ; i < t.length;i++){
        while(!s.isEmpty() && t[i] > t[s.peek()]){
            int index = s.pop();
            res[index] = i - index;
        }
        s.push(i);
    }
    return res;

}