Problem: 739. 每日溫度

題目描述

思路

若本題目使用暴力法則會(huì)超時(shí)，故而使用單調(diào)棧解決：

1.創(chuàng)建結(jié)果數(shù)組res，和單調(diào)棧stack；
2.循環(huán)遍歷數(shù)組temperatures：

2.1.若當(dāng)stack不為空同時(shí)棧頂所存儲(chǔ)的索引對(duì)應(yīng)的氣溫小于當(dāng)前的氣溫，則跟新res中對(duì)應(yīng)位置的值；
2.2.每次向stack中存入每日氣溫的索引下標(biāo)

復(fù)雜度

時(shí)間復(fù)雜度:

$O(n)$；其中$n$是數(shù)組temperatures的大小

空間復(fù)雜度:

$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;}
}