【刷题】力扣739.每日温度

739. 每日温度

一开始错误代码：

class Solution { public: vector<int> dailyTemperatures(vector<int>& temperatures) { stack<int> st; int len=temperatures.size(); vector<int> res(len,0); // st.push(0); for(int i=0;i<len;i++){ //如果新进来的元素符合单调减的栈，直接入栈 if(!st.empty() && temperatures[i]<=temperatures[st.top()]){ st.push(i);//存下标 方便记录差了几天 } else{//如果大的话就依次找栈之前的元素 while(!st.empty() && temperatures[i]>temperatures[st.top()]){ // res[st.top()]=i-st.top(); res[i]++; st.pop(); } st.push(i); } } return res; } };

我一开始以为：while 循环每执行一次，就代表多等了一天

但实际是：while 循环每执行一次，就找到了一个元素的答案，答案 =i - st.top()（直接算出间隔天数）

总结就是：res[i]++是在给“当前温度”累加，但“当前温度”是那个更大的温度，它不应该在这里被加。应该给“被弹出的栈顶温度”赋值间隔天数。

正确代码如下：

class Solution { public: vector<int> dailyTemperatures(vector<int>& temperatures) { stack<int> st; int len=temperatures.size(); vector<int> res(len,0); // st.push(0); for(int i=0;i<len;i++){ //如果新进来的元素符合单调减的栈，直接入栈 if(!st.empty() && temperatures[i]<=temperatures[st.top()]){ st.push(i);//存下标 方便记录差了几天 } else{//如果大的话就依次找栈之前的元素 while(!st.empty() && temperatures[i]>temperatures[st.top()]){ res[st.top()]=i-st.top(); st.pop(); } st.push(i); } } return res; } };

上面是根据逻辑写出来的，会有冗余代码，优化后如下：

class Solution { public: vector<int> dailyTemperatures(vector<int>& temperatures) { stack<int> st; int len=temperatures.size(); vector<int> res(len,0); for(int i=0;i<len;i++){ while(!st.empty() && temperatures[i]>temperatures[st.top()]){ res[st.top()]=i-st.top(); st.pop(); } st.push(i); } return res; } };