739. 每日温度 (opens new window)

单调栈

解题思路：维护一个单调栈，保存当前数组元素。具体来说，如果当前元素比栈顶元素还小，那么当前元素入栈，否则说明当前元素就是栈顶元素右边遇到的第一个大的元素，因此栈顶元素依次出栈并记录天数。因此整个栈从栈底到栈顶维护的是一个递减序列。

核心：这里能用栈的原因在于，需要找到右边并且是第一个大的元素，同时满足这两个条件因此可以使用栈。栈能够保证第一个匹配这个特性，类似于括号匹配也是这个原因。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
            Stack<Integer> stack=new Stack<>();
            stack.push(0);
            for(int i=1;i<temperatures.length;i++){
                int peek=stack.peek();
                while(!stack.isEmpty()&&temperatures[peek]<temperatures[i]){
                    temperatures[peek]=i-peek;
                    stack.pop();
                    if(!stack.isEmpty()) peek=stack.peek();
                }
                stack.push(i);
            }
            while(!stack.isEmpty()){
                int index=stack.pop();
                temperatures[index]=0;
            }
            return temperatures;
    }
}