代码随想录算法训练营第六十天|739. 每日温度、496.下一个

739. 每日温度 

首先想到暴力求解

遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次

单调栈里存放元素的下标i

情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况

情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况

情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

vector<int>dailyTemperatures(vector<int>&T){// 递增栈stack<int>st;vector<int>result(T.size(),0);st.push(0);for(inti=1;i<T.size();i++){if(T[i]<T[st.top()]){// 情况一st.push(i);}elseif(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);}}returnresult;}

496.下一个更大元素 I  

定义一个和nums1一样大小的数组result来存放结果，初始化为-1

遍历nums2的过程中，判断nums2[i]是否在nums1中出现过，根据nums1元素的下标来更新result数组

栈头到栈底的顺序，要从小到大，也就是保持栈里的元素为递增顺序

情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况

此时满足递增栈（栈头到栈底的顺序），所以直接入栈。

情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况

如果相等的话，依然直接入栈，因为我们要求的是右边第一个比自己大的元素，而不是大于等于！

情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

此时如果入栈就不满足递增栈了，这也是找到右边第一个比自己大的元素的时候。

判断栈顶元素是否在nums1里出现过，（注意栈里的元素是nums2的元素），如果出现过，开始记录结果。

vector<int>nextGreaterElement(vector<int>&nums1,vector<int>&nums2){stack<int>st;vector<int>result(nums1.size(),-1);if(nums1.size()==0)returnresult;unordered_map<int,int>umap;// key:下标元素，value：下标for(inti=0;i<nums1.size();i++){umap[nums1[i]]=i;}st.push(0);for(inti=1;i<nums2.size();i++){while(!st.empty()&&nums2[i]>nums2[st.top()]){if(umap.count(nums2[st.top()])>0){// 看map里是否存在这个元素intindex=umap[nums2[st.top()]];// 根据map找到nums2[st.top()] 在 nums1中的下标result[index]=nums2[i];}st.pop();}st.push(i);}returnresult;}