长沙做网站推广哪家好网上在线做家教网站

Problem: 739. 每日温度

题目描述

思路

若本题目使用暴力法则会超时，故而使用单调栈解决：

1.创建结果数组res，和单调栈stack；
2.循环遍历数组temperatures：

2.1.若当stack不为空同时栈顶所存储的索引对应的气温小于当前的气温，则跟新res中对应位置的值；
2.2.每次向stack中存入每日气温的索引下标

复杂度

时间复杂度:

$O(n)$；其中$n$是数组temperatures的大小

空间复杂度:

$O(n)$

Code

class Solution {/*** Daily Temperatures** @param temperatures Given array* @return int[]*/public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;Stack<Integer> stack = new Stack<>();int[] res = new int[n];for (int i = n - 1; i >= 0; --i) {while (!stack.isEmpty() && temperatures[stack.peek()] <= temperatures[i]) {stack.pop();}res[i] = stack.isEmpty() ? 0 : stack.peek() - i;stack.push(i);}return res;}
}