题解 | JAVA #每日温度# [P0-T2]

单调栈直接套娃 记口诀就行:
找右边的就从右往左，找左边的从左往右
找小的就单调递增，找大的就单调递减

这题是找右边的大的，那就从右往左loop, 建单调递减栈

O(n), O(n)

import java.util.*;

public class Solution {
    public int[] temperatures (int[] temperatures) {
      int[] ans = new int[temperatures.length];
      
      // stack规则： 从右向左push index，栈单调递减(相对于temp[index])
      Deque<Integer> stack = new ArrayDeque<>();
      for (int i = temperatures.length-1; i >= 0; i--) {
        while (!stack.isEmpty() && temperatures[stack.peek()] <= temperatures[i])
          stack.pop();
        
        ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;
        stack.push(i);
      }
      
      return ans;
    }
}