思路和时间复杂度
- 思路:要求找出第一个大的元素,因此从左往右找到比栈顶大的元素就收集结果并且更新栈,弹出栈顶,如果是小于等于栈的元素,就入栈,因为跟所求的元素没什么关系,此时栈内从栈顶到栈底是单调递增的
- 时间复杂度:
代码
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;
}
};