北京住房与城乡建设部网站,wordpress音乐插件,手机官网制作,大型建设网站制作【力扣】739. 每日温度
给定一个整数数组 temperatures #xff0c;表示每天的温度#xff0c;返回一个数组 answer #xff0c;其中 answer[i] 是指对于第 i 天#xff0c;下一个更高温度出现在几天后。如果气温在这之后都不会升高#xff0c;请在该位置用 0 来代替。
…【力扣】739. 每日温度
给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用 0 来代替。
示例 1: 输入: temperatures [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]
示例 2: 输入: temperatures [30,40,50,60] 输出: [1,1,1,0]
示例 3: 输入: temperatures [30,60,90] 输出: [1,1,0]
提示 1 temperatures.length 1 0 5 10^5 105 30 temperatures[i] 100
题解 通常是一维数组要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置此时就要想到可以用单调栈。时间复杂度为O(n)。 单调栈的本质是空间换时间因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素优点是整个数组只需要遍历一次。更直白来说就是用一个栈来记录遍历过的元素因为遍历数组的时候不知道之前都遍历了哪些元素以至于遍历一个元素找不到是不是之前遍历过一个更小的所以需要用一个容器这里用单调栈来记录我们遍历过的元素。
使用单调栈的时候首先要明确如下几点 单调栈里存放的元素是什么 单调栈里只需要存放元素的下标 i i i 就可以了如果需要使用对应的元素直接 T [ i ] T[i] T[i] 就可以获取。 单调栈里元素是递增呢 还是递减呢从栈头到栈底的顺序 如果求一个元素右边第一个更大元素单调栈就是递增的如果求一个元素右边第一个更小元素单调栈就是递减的。 本题其实就是找找到一个元素右边第一个比自己大的元素此时就应该想到用单调栈。
class Solution {
public static int[] dailyTemperatures(int[] temperatures) {//单调栈只存放下标StackInteger stack new Stack();int[] result new int[temperatures.length];//先放入第一个元素下标stack.push(0);for (int i 1; i temperatures.length; i) {//情况1小于if (temperatures[i] temperatures[stack.peek()]) { stack.push(i);}//情况2等于else if (temperatures[i] temperatures[stack.peek()]){ stack.push(i);}//情况3大于else {while (!stack.isEmpty() (temperatures[i] temperatures[stack.peek()])) { int index stack.peek();result[index] i - index;stack.pop();}stack.push(i);}}return result;}
}双端队列实现
class Solution {
public static int[] dailyTemperatures(int[] temperatures) {//单调栈只存放下标DequeInteger stack new LinkedList();int[] result new int[temperatures.length];stack.push(0);for (int i 1; i temperatures.length; i) {//情况1小于if (temperatures[i] temperatures[stack.peek()]) { stack.push(i);}//情况2等于else if (temperatures[i] temperatures[stack.peek()]){ stack.push(i);}//情况3大于else {while (!stack.isEmpty() (temperatures[i] temperatures[stack.peek()])) { int index stack.peekFirst();result[index] i - index;stack.pop();}stack.push(i);}}return result;}
}
