Problem: 739. 每日溫度

題目描述

思路

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

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

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

復(fù)雜度

時間復(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;}
}