这个题如何用栈解呢？
每日温度
今天又给大家挑了一道十分经典的题目，也是一道面试常考题目，所以大家记得打卡啊，我们先来看一下题目描述，题目很容易理解，而且用暴力法也很容易实现，因为这个题目出现了我们的栈的模块，大家能不能用栈实现呢？
为保证严谨性，文章中的所有代码均经过测试，大家可以放心食用。
题目描述：
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例1：
输入：temperatures = [73, 74, 75, 71, 69, 72, 76, 73] 输出：arr = [1, 1, 4, 2, 1, 1, 0, 0]
示例2：
输入：temperatures = [30,30,31,45,31,34,56] 输出：arr = [2,1,1,3,1,1,0]
题目解析：题目是不是很容易理解啊，就是为了我们找到当前值的后面比其大第一个的数，他俩之间相差几位。比如示例1中，75的下标为2，75的后面比它大的值为76下标为6，6-2=4所以arr[2]=4;
暴力解：
j 指针每次都初始化在i指针后一位，然后遍历数组，找到比其大的值就赋值给arr数组，直至i指针遍历结束。
题目代码：
class Solution {
public int[] dailyTemperatures(int[] T) {
//创建输出数组
int[] arr = new int[T.length];
//遍历输入数组
for (int i = 0; i < T.length; i++) {
//定义j指针
int j = i + 1;
//找到比其大的值
while (j < T.length && T[i] >= T[j]) {
j++;
}
//两种情况的赋值，一种是找到了比其大的值，一种是没找到赋值为0
if(j < T.length && T[i] < T[j]){
arr[i] = j-i;
}else{
arr[i] = 0;
}
}
return arr;
}
}
栈：
下面我们来看一下如何用栈完成这个题目，我们先看动图了解下思路。
注：栈中的括号内的值，代表索引对应的元素，我们的入栈的为索引值，为了便于理解将其对应的值写在了括号中
解题思路：我们遍历数组时，会先跟栈顶索引对应的元素进行对比，如果小于该值则入栈，如果大于则将栈顶元素出栈，新的元素入栈。例如栈顶为69，新的元素为72，则69出栈，72入栈。并赋值给arr，69的索引为4，72的索引为5，则arr[4] = 5-4=1;
题目代码：
class Solution {
public int[] dailyTemperatures(int[] T) {
//得到数组长度
int len = T.length;
//创建一个栈，用于存T的索引
Stack<Integer> stack = new Stack<>();
//返回的数组
int[] arr = new int[len];
//遍历数组
for(int i = 0; i < len; i++){
//当指针指向的当前值大于栈顶元素对应值时则队数组赋值。
while(!stack.isEmpty() && T[i] > T[stack.peek()]){
arr[stack.peek()] = i - stack.pop();
}
//栈为空时和当前值小于等于栈顶元素时入栈
stack.push(i);
}
return arr;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-11-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
