链接

第一次暴力提交错误，超时了：

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> res(n,0);for(int i = 0;i<n;i++){int j = i+1;while(j<n){if(temperatures[j]>temperatures[i]){res[i] = j-i;break;}else{++j;}}}return res;}
};

强大的数据：
 

第二次正确提交：

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> res(temperatures.size());stack<int> s;for(int i = temperatures.size()-1;i>=0;i--){while(s.size()&&temperatures[i]>=temperatures[s.top()]){s.pop();}if(s.size()){res[i] = s.top()-i;}s.push(i);}return res;}
};

注意：s是一个栈，里面存储的是下标，不是温度。这个题是单调栈的模板题。

单调栈其实就是对于暴力做法的优化，第一个优化：本来遍历到 i 时，你要利用for循环去右边遍历到比你大的元素，现在不用了，我们一开始就从右边起手，然后把 子数组全部存起来，这样遍历到 i 的时候，你在栈里找你要的答案就行了。这还不够，因为本质还是和for循环一样的。

所以第二个优化：遍历到 j 时，我们就判断，栈顶元素与 j 之间的大小，如果 j 大于等于栈顶元素的话，那就应该删掉栈顶元素，为什么？因为 j 比你栈顶有先发优势，人家下标更小，更受左边的 i 的青睐，你栈顶元素虽然有可能比 i 大，但是架不住 j 离得近，近水楼台先得月！

这就是单调栈，对于两层for 循环的优化。

单调栈讲解