力扣-单调栈-739-每日温度
目录
力扣-单调栈-739 每日温度
思路和时间复杂度
- 思路：要求找出第一个大的元素，因此从左往右找到比栈顶大的元素就收集结果并且更新栈，弹出栈顶，如果是小于等于栈的元素，就入栈，因为跟所求的元素没什么关系，此时栈内从栈顶到栈底是单调递增的
- 时间复杂度：
代码
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<int> res(temperatures.size(), 0);
stack<int> st;
st.push(0);
for(int i = 1; i < temperatures.size(); i++){
if(temperatures[i] < temperatures[st.top()]){
st.push(i);
}else if(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;
}
};