leetcode 739. 每日温度
请根据每日气温列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0 来代替。
题解:
1.一个数组,每日气温列表
2.要观测更高的气温,需要等多少天
3.在这个气温之后都不会升高,等待0天
示例 1:
temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的
输出:[1, 1, 4, 2, 1, 1, 0, 0]。
提示:气温列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数
解题思路:栈的应用
-
因为这里计算的是等待天数,所以记录气温的下标,使用下标做计算
-
先把第一个下标0放入栈中,往后遍历每个气温值
-
如果气温变高了,把栈顶元素取出,用当前气温下标减去栈顶元素,即得到栈顶元素下标所在的气温到当前气温的相隔天数(下标差)
-
如果气温变低了,直接把当前气温下标压入栈中
-
最后如果栈中有剩余下标,则是从该气温后都不会升高,赋值0
C/C++题解:
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
stack<int> st; //使用栈
st.push(0); //最开始push(0)开始
for(int idx = 1;idx < T.size(); idx++){
//遍历后边每一个元素,如果栈不空
while(!st.empty() && idx < T.size()){
int tpi = st.top();//取栈顶元素比较
if(T[idx] > T[tpi]){//后面的数比前面的大
st.pop();//则把前面数的下标取出
T[tpi] = idx - tpi;}//计算下次更高温度隔几天,即下标差
else break;}//每次把当前值的下标加到栈里,后面遇到大的就取出
st.push(idx);}
//最后留在栈里的,即气温在这之后都不会升高
while(!st.empty()){
int tpi = st.top();
st.pop();
T[tpi] = 0;}//对应位置上写0
return T;}};//返回整个数组
Debug结果:
Java题解:
class Solution {
public int[] dailyTemperatures(int[] T) {
Stack<Integer> st = new Stack<Integer>(); //使用栈
st.push(0); //最开始push(0)开始
for(int idx = 1;idx < T.length; idx++){
//遍历后边每一个元素,如果栈不空
while(!st.isEmpty() && idx < T.length){
int tpi = st.peek();//取栈顶元素比较
if(T[idx] > T[tpi]){//后面的数比前面的大
st.pop();//则把前面数的下标取出
T[tpi] = idx - tpi; }//计算下次更高温度隔几天,即下标差
else break;}//每次把当前值的下标加到栈里,后面遇到大的就取出
st.push(idx);}
//最后留在栈里的,即气温在这之后都不会升高
while(!st.isEmpty()){
int tpi = st.pop();
T[tpi] = 0;}//对应位置上写0
return T;}}//返回整个数组
Debug结果:
Python题解:
class Solution(object):
def dailyTemperatures(self, T):
""":type T: List[int]:rtype: List[int]"""
st = [] #模拟栈
st.append(0) #最开始push(0)开始
for idx in range(1, len(T)):
#遍历后边每一个元素,如果栈不空
while st and idx < len(T):
tpi = st[-1] #取栈顶元素比较
if T[idx] > T[tpi]: #后面的数比前面的大
st.pop() #则把前面数的下标取出
T[tpi] = idx - tpi #计算下次更高温度隔几天,即下标差
else: break
#每次把当前值的下标加到栈里,后面遇到大的就取出
st.append(idx)
#最后留在栈里的,即气温在这之后都不会升高
while st:
tpi = st.pop()
T[tpi] = 0 #对应位置上写0
return T #返回整个数组
Debug结果:
更多题解移步公众号免费获取