739. 每日温度（高频题）

解题思路

这题是 “Next Greater Elment”类型的题目，直接用单调栈 （栈底元素最大）。

代码

class Solution {
        public int[] dailyTemperatures(int[] T) {
        int[] result = new int[T.length];


        Stack<Integer> stack = new Stack<>();
        for(int i = T.length - 1; i >=0; i--) {
            // 如果栈不为空且当前温度大于栈顶温度
            // 由于是逆序遍历，所以栈中索引对应的温度不可能比其之前某天温度高
            // 所以将栈中存取的温度出栈，直到栈为空或当前温度小于栈顶索引对应温度
            while (!stack.isEmpty() && T[i] >= T[stack.peek()]) {
                stack.pop();
            }
            // 1.如果栈不为空，且当前温度小于栈顶温度，由于是逆序遍历
            // 所以栈顶温度是比当前温度高的一天，
            // 栈顶温度对应的索引减去当前温度的索引就是差的天数
            // 2.如果栈为空，说明当前温度之后没有比其高的温度，根据题意值为0
            result[i] = stack.isEmpty() ? 0 : stack.peek() - i;
            stack.push(i);
        }
        return result;
    }
}