问题描述

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

给你一个数组，代表每天的温度，分别求出需要等待多少天，才能等到大于当天温度的天气。

如果等不到，就返回0。

举个例子：

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

解法1

本题可以使用单调递减栈思想。

注意三点：

第一，需要构建单调递减的栈。

第二，栈中存储的是索引，便于计算天数。

第三，从右往左遍历。

来看下实现：

class Solution {
    public int[] dailyTemperatures(int[] T) {

        int n = T.length;
        int[] ans = new int[n];
        // Store indices.
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        for (int i = n - 1; i >= 0; i--){
            int cur = T[i];
            while (!stack.isEmpty() && cur >= T[stack.peek()]){
                stack.pop();
            }
            ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;
            stack.push(i);
        }
        return ans;
    }
}

Enjoy it !