【小白刷题之路Day28】leetcode739 每日温度（双指针暴力法，单调栈）（单调栈的初次学习使用）...

leetcode739 每日温度 根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。 提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/daily-temperatures 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 方法1：暴力法的双指针优化

第一次提交代码

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

 

除了i指示回溯的左端外，引入p指示回溯的右端。

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

 

 

 

最后优化代码： （开头特殊例子检测可以省略，不影响结果）

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

暴力法时间复杂度为O(n^2)，优化后仍然不变，但是不优化无法通过案例（无数个“76”）

 

单调栈法（Monotone Stack）

本题是一个很经典、很基础的单调栈的例子

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

总结：

本题是单调栈的经典题、基础题熟悉了单调栈的原理和使用，很厉害的数据结构，被单调栈的简单优雅的代码迷住了！！

 

转载于:https://www.cnblogs.com/ACStrive/p/11601181.html