代码随想录算法【Day47】
单调栈
单调栈：保持栈里面的元素是递增的或者递减的
问题场景：求当前元素左边或者右边第一个比当前元素大或者小的元素
单调栈的作用：存放遍历过的元素的下标
遍历过程：
求当前元素右边第一个比当前元素大的元素，单调栈内的元素（从栈顶到栈底）为单调递增。
使用result[i]来记录结果，表示下标为i的元素与右边第一个比它大的元素的距离。
若当前遍历的元素没有栈顶元素大，则入栈；若当前遍历的元素比栈顶元素大，则栈顶元素弹出，同时更新刚刚被弹出的栈顶元素的result[i]值
739.每日温度
-
情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况：直接入栈
-
情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况：直接入栈
-
情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况：当前元素与栈顶元素进行比对，若大于栈顶元素，则更新result数组
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
stack<int> st;
vector<int> result(T.size(), 0);
st.push(0);
for(int i = 1; i < T.size(); i++){
if(T[i] <= T[st.top()]){
st.push(i);
}
else{
while(!st.empty() && T[i] > T[st.top()]){
result[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
}
return result;
}
};