代码随想录算法【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;   } };