739.每日温度

一、题目

请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例一：

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

示例二：

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例三：

输入: temperatures = [30,60,90]
输出: [1,1,0]

二、相关链接

• 题目链接：https://leetcode-cn.com/problems/daily-temperatures/
• 参考题解：https://leetcode-cn.com/problems/daily-temperatures/solution/leetcode-tu-jie-739mei-ri-wen-du-by-misterbooo/

三、解题思路

• 解法：单调栈
• 思路：将每一天的温度(存下标)压入栈，后面压入的时候把前面低于的取出来计算天数(保证栈底到栈顶是递增的)

四、代码

public class DailyTemperatures {
  public int[] dailyTemperatures(int[] temperatures) {
    //可以参考左视图，如果一个温度把之前的温度的盖住了，说明比他高，就可以赋值了，并移除状态
    //存下标吧，存value有问题
    Stack<Integer> stack = new Stack<>();
    //初始化个结果吧，默认值是0(不要直接操作原数组，会多一个for操作)
    int result[] = new int[temperatures.length];
    for(int i=0;i<temperatures.length;i++){
      //当栈不为空时，从上取比当前数小的取出并设置result
      while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){
        //计算相隔天数并写入result
        int index = stack.pop();
        result[index] = i - index;
      }
      stack.push(i);
    }

    return result;
  }

  /**
   * 例子：
   *  输入：[73,74,75,71,69,72,76,73]
   *  输出：[1,1,4,2,1,1,0,0]
   */
  public static void main(String[] args) {
    int nums[] = new int[]{73,74,75,71,69,72,76,73};
    int result[] = new DailyTemperatures().dailyTemperatures(nums);
    for(int i:result){
      System.out.print(i+",");
    }
  }
}

五、总结

• 难度：简单看题解后可完成