739. Daily Temperatures
Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.
For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].
Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].
给定数组, 找出每个元素后面最近的比他大的数, 暴力解法当然可破.研究一下最优解
使用栈,第一个元素先入栈, 后面遍历每个元素时,先看栈顶元素是否符合, num[i]>stack.top(), 若符合我们就知道栈顶元素对应原数组的索引,把对应的结果填上.
那么这里为什么只用判断栈顶元素呢? 好像应该把栈遍历一遍对不对. 其实不用. 因为栈的元素一定是从大到小排序的.
class Solution { public: vector<int> dailyTemperatures(vector<int>& T) { vector<int> res(T.size(),0),st; for(int i=0;i<T.size();++i) { while(!st.empty()&&T[i]>T[st.back()]) { res[st.back()]=i-st.back(); st.pop_back(); } st.push_back(i); } return res; } };
由于栈的入栈和出栈实际上有拷贝元素的问题, 使用数组+索引可以稍微更快点.
这里测试c++版本好像也没有快多少, 200ms和180ms的区别,不知道为何原答案Java版本差了那么多
class Solution { public: vector<int> dailyTemperatures(vector<int>& T) { vector<int> res(T.size(),0),st(T.size()); int idx=-1; for(int i=0;i<T.size();++i) { while(idx>-1&&T[i]>T[st[idx]]) { res[st[idx]]=i-st[idx]; --idx; } st[++idx]=i; } return res; } };