链接：https://leetcode-cn.com/problems/daily-temperatures/

解题思路：栈

初始化：

  • 初始化一个单调递减栈Stack<Integer> stack = new Stack<>() 用来存放温度数组的下标
  • 声明返回数组 res

算法流程：

  • 从头遍历温度数组 temperatures
    • 如果当前栈为空，则将该位置下标 i 添加到栈中
    • 如果当前栈不为空
      • 当遍历到的温度 temperatures[i] 大于栈顶所表示的温度 temperatures[stack.peek()] 时，我们就执行循环出栈的操作，直至当前栈满足一个单调递减栈；每次的出栈操作，我们都可以确定返回数组 res 的一个值
      • 向栈中添加元素 i
  • 最后返回结果集res

流程示意图：

image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png

代码

  1. class Solution {
  2.     public int[] dailyTemperatures(int[] temperatures) {
  3.         int[] res = new int[temperatures.length];
  4.         Stack<Integer> stack = new Stack<>();
  5.         for(int i = 0; i < temperatures.length; i++){
  6.             if(stack.isEmpty()){
  7.                 stack.push(i);
  8.             }else {
  9.                 while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){    
  10.                     int j = stack.pop();
  11.                     res[j] = i - j;              
  12.                 }
  13.                 stack.push(i);
  14.             }
  15.         }
  16.         return res;
  17.     }
  18. }

复杂度分析

  • 时间复杂度

从头至尾遍历了一次数组，时间复杂度为：

  • 空间复杂度

我们使用了栈这种辅助数据结构，额外空间复杂度为：